Atcoder.chokudai_S001_h LIS

1.Problem
https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_h

2.Idea
Using BIT Max Range Query

3.Source

 const int N = 100005;  
 //////////////////////////////  
 class BIT {  //1 -indexed
      const int n;  
      vector<Int> bit;  
 public:  
      BIT(int _n = 0) : n(_n), bit(n + 1, 0) {}  
      void add(int i, const Int x = 1) { for (i++; i <= n; i += i&-i) bit[i] += x; }  
      Int sum(int i) { Int x = 0; for (i++; i; i -= i & -i) x += bit[i]; return x; }  
      Int sum(int i, int j) { return sum(j) - sum(i - 1); }  
 };  
 struct FenwickTreeMin {  
      vector<int> bit;  //0 -indexed
      int n;  
      const int INF = (int)1e9;  
      FenwickTreeMin(int n) {  
           this->n = n;  
           bit.assign(n, INF);  
      }  
      FenwickTreeMin(vector<int> a) : FenwickTreeMin(a.size()) {  
           for (size_t i = 0; i < a.size(); i++)  
                update(i, a[i]);  
      }  
      int getmin(int r) {  
           int ret = INF;  
           for (; r >= 0; r = (r & (r + 1)) - 1)  
                ret = min(ret, bit[r]);  
           return ret;  
      }  
      void update(int idx, int val) {  
           for (; idx < n; idx = idx | (idx + 1))  
                bit[idx] = min(bit[idx], val);  
      }  
 };  
 struct FenwickTreeMax {  
      vector<int> bit;  // 0 - indexed
      int n;  
      FenwickTreeMax(int n) {  
           this->n = n;  
           bit.assign(n, -INF);  
      }  
      FenwickTreeMax(vector<int> a) : FenwickTreeMax(a.size()) {  
           for (size_t i = 0; i < a.size(); i++)  
                update(i, a[i]);  
      }  
      int getMax(int r) {  
           int ret = -INF;  
           for (; r >= 0; r = (r & (r + 1)) - 1)  
                ret = max(ret, bit[r]);  
           return ret;  
      }  
      void update(int idx, int val) {  
           for (; idx < n; idx = idx | (idx + 1))  
                bit[idx] = max(bit[idx], val);  
      }  
 };  
 int n;  
 int a[N];  
 void solve()  
 {  
      cin >> n;  
      REP(i, n) cin >> a[i];  
      map<int, int> mp;  
      REP(i, n) mp[a[i]] = 0;  
      int i = 0;  
      for (auto it = mp.begin(); it != mp.end(); it++) {  
           it->second = i;  
           i++;  
      }  
      FenwickTreeMax ftm(n);  
      REP(i, n) {  
           int cur = mp[a[i]];  
           int tmp = ftm.getMax(cur - 1);  
           if(tmp == -INF) ftm.update(cur, 1);  
           else ftm.update(cur, tmp + 1);  
      }  
      cout << ftm.getMax(n - 1) << endl;  
 }