tuki2501

LIS_BIT.cpp

Dec 4th, 2021
788
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. void chmax(int &a, int b) {
  7.   if (a < b) a = b;
  8. }
  9.  
  10. struct BIT {
  11.   int n; vector<int> bit;
  12.   BIT(int n): n(n), bit(n + 1) {}
  13.   void update(int i, int v) {
  14.     for (; i <= n; i += i & -i) {
  15.       chmax(bit[i], v);
  16.     }
  17.   }
  18.   int get(int i) {
  19.     int v = 0;
  20.     for (; i; i -= i & -i) {
  21.       chmax(v, bit[i]);
  22.     }
  23.     return v;
  24.   }
  25. };
  26.  
  27. signed main() {
  28.   cin.tie(0)->sync_with_stdio(0);
  29.   int n; cin >> n;
  30.   vector<int> a(n), v(n);
  31.   for (int i = 0; i < n; i++) {
  32.     cin >> a[i];
  33.     v[i] = a[i];
  34.   }
  35.   sort(v.begin(), v.end());
  36.   v.resize(unique(v.begin(), v.end()) - v.begin());
  37.   for (auto &i : a) {
  38.     i = v.end() - lower_bound(v.begin(), v.end(), i);
  39.   }
  40.   int ans = 0;
  41.   BIT bit(n);
  42.   for (auto &i : a) {
  43.     int t = bit.get(i);
  44.     chmax(ans, t + 1);
  45.     bit.update(i, t + 1);
  46.   }
  47.   cout << ans << '\n';
  48. }
  49.  
RAW Paste Data