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;  
 }  

POJ.3214 Heap

1.Problem
http://poj.org/problem?id=3214

2.Idea
Post-Order traversal and LIS.

3.Source

 #include<iostream>  
 #include<cstdio>  
 #include<algorithm>  
 #include<queue>  
 #define maxn 0x7fffffff  
 using namespace std;  
 const int N=2e6;  
 int a[N];  
 int n,x=0;  
 int st[N];  
 vector<int>v;  
 void solve(int k,int& d){  
   if(2*k<=x) solve(k<<1,d);  
   if(2*k+1<=x) solve((k<<1)+1,++d);  
   v.push_back(a[k]-d);  
 }  
 int main()  
 {  
   scanf("%d",&n);  
   while(scanf("%d",&a[++x])!=EOF);  
   int d=0;  
   x--;  
   solve(1,d);  
   st[0]=-maxn;  
   int top=0;  
   for(int i=0,len=v.size();i<len;i++){  
     if(v[i]>=st[top])  
       st[++top]=v[i];  
     else{  
       int k=upper_bound(st,st+top+1,v[i])-st;  
       st[k]=v[i];  
     }  
   }  
   printf("%d\n",x-top);  
   return 0;  
 }