Shared code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
 
using ll = long long;
 
class SegmentTree{
private:
  std::vector<int> aint;
  int n;
 
  int join(int x, int y) {
    return std::max(x, y);
  }
  
  void _update(int node, int from, int to, int x, int val) {
    if(from < to) {
      int mid = (from + to) / 2;
      if(x <= mid)
        _update(node * 2, from, mid, x, val);
      else
        _update(node * 2 + 1, mid + 1, to, x, val);
      aint[node] = join(aint[node * 2], aint[node * 2 + 1]);
    } else
      aint[node] = val;
  }
 
  int _query(int node, int from, int to, int x, int y) {
    if(from == x && to == y) {
      return aint[node];
    } else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return _query(node * 2, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return _query(node * 2 + 1, mid + 1, to, x, y);
      else
        return join(_query(node * 2, from, mid, x, mid),
                    _query(node * 2 + 1, mid + 1, to, mid + 1, y));
    }
  }
  
  void _print(int node, int from, int to) {
    if(from < to) {
      int mid = (from + to) / 2;
      _print(node * 2, from, mid);
      _print(node * 2 + 1, mid + 1, to);
    } else
      std::cout << aint[node] << " ";
  }
 
public:
  SegmentTree(int n_) {
    n = n_;
    aint.resize(1 + 4 * n);
  }
  
  void update(int x, int val) {
    _update(1, 1, n, x, val);
  }
  
  int query(int x, int y) {
    return _query(1, 1, n, x, y);
  }
 
  void print() {
    std::cout << "Print array\n";
    _print(1, 1, n);
    std::cout << '\n';
  }
};
 
/*
One easy way to normalize an array is to first create a copy of it. 
Let 'v' be the array to be normalized and 'aux' its duplicate.
Then, sort the copy and erase the dublicates.
Thus, 'aux' contains all the distinct elements in 'v'.
Now, we simply have to find for each element in 'v' its position in 'aux'. 
This can be easily done using binary search or the STL-provided lower_bound function.
*/
 
void normalize(std::vector<int> &v) {
  std::vector<int> aux = v;
  std::sort(aux.begin(), aux.end());
  aux.erase(std::unique(aux.begin(), aux.end()), aux.end());
  for(int i = 0; i < v.size(); i++)
    v[i] = std::lower_bound(aux.begin(), aux.end(), v[i]) - aux.begin() + 1;
}
 
int main() {
  int n;
  std::cin >> n;
  std::vector<int> v(n);
  for(int i = 0; i < n; i++)
    std::cin >> v[i];
  normalize(v);
 
  SegmentTree segTree(n);
  for(int i = 0; i < n; i++) {
    int result = 0;
    if(1 < v[i])
      result = segTree.query(1, v[i] - 1);
    else
      result = 0;
    segTree.update(v[i], result + 1);
  }
  std::cout << segTree.query(1, n) << '\n';
  return 0;
}