Codeforces 486E LIS of Sequence --树状数组求LIS

题意： 一个序列可能有多个最长子序列，现在问每个元素是以下三个种类的哪一类：

1.不属于任何一个最长子序列

2.属于其中某些但不是全部最长子序列

3.属于全部最长子序列

解法： 我们先求出dp1[i]表示1~i 的最长递增子序列长度, dp2[i]表示 n~i 的最长递减子序列长度（严格增减），这里我们可以用维护最大值的树状数组来解决，开始还以为要用nlogn求LIS的那种算法，当然那样应该也可以，这里元素值是1~10^5的，可以直接用树状数组，如果元素值任意的话，我们离散化一下也可以用树状数组。

求出dp1[],dp2[]后，我们先判断第1类： 当dp1[i] + dp2[i] != Length+1 （Length为LIS长度）的话，说明前后不一致，不属于最长子序列。

再判第3类，如果某个元素属于其中的一些最长子序列，那么他的dp1值一定不是唯一的，还有别的dp1值也等于他的dp1值，如1 2 3 5，那么dp1[2] = dp1[3] = 2.

所以先把第1类判掉以后，不考虑第1类，看dp1值是否重复来判第3类。第1,3类判完剩下的就是第2类了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#define lll __int64
using namespace std;
#define N 100107

int a[N],c[N],n,MAX;
int dp1[N],dp2[N];
string S;
int lowbit(int x) { return x&-x; }
void modify(int up,int x,int val) {
    if(up) {
        while(x <= MAX) {
            c[x] = max(c[x],val);
            x += lowbit(x);
        }
    }
    else {
        while(x > 0) {
            c[x] = max(c[x],val);
            x -= lowbit(x);
        }
    }
}
int getmax(int up,int x) {
    int maxi = 0;
    if(up) {
        while(x > 0) {
            maxi = max(maxi,c[x]);
            x -= lowbit(x);
        }
    }
    else {
        while(x <= MAX) {
            maxi = max(maxi,c[x]);
            x += lowbit(x);
        }
    }
    return maxi;
}
map<int,int> mp;

int main()
{
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        S = "#"; MAX = 0;
        for(i=1;i<=n;i++) cin>>a[i], S += "0", MAX = max(MAX,a[i]);
        memset(c,0,sizeof(c));
        int LIS = 0;
        for(i=1;i<=n;i++) {
            int maxi = getmax(1,a[i]-1);
            dp1[i] = maxi+1;
            LIS = max(LIS,dp1[i]);
            modify(1,a[i],dp1[i]);
        }
        memset(c,0,sizeof(c));
        for(i=n;i>=1;i--) {
            int maxi = getmax(0,a[i]+1);
            dp2[i] = maxi+1;
            modify(0,a[i],dp2[i]);
        }
        mp.clear();
        for(i=1;i<=n;i++) {
            if(dp1[i] + dp2[i] - 1 != LIS) S[i] = '1';
            else mp[dp1[i]]++;
        }
        for(i=1;i<=n;i++)
            if(S[i] != '1' && mp[dp1[i]] == 1) S[i] = '3';
        for(i=1;i<=n;i++)
            if(S[i] == '0') S[i] = '2';
        cout<<S.substr(1,n)<<endl;
    }
    return 0;
}