codeforces 486 E. LIS of Sequence（dp）

题目链接：http://codeforces.com/contest/486/problem/E

题意：给出n个数，如果一个数满足不属于最长递增序列，那么输出1，如果属于最长递增序列但是不属于所有最长递增序列的输出2。

如果属于所有最长递增序列的输出3。

 

题解：这里要用点技巧，不妨设dpBefore[i]表示以第i位为结尾的最长递增序列长，dpAfter[i]表示以第i位为结尾的最长递增序列长。

然后只要满足dpBefore[i]+dpAfter[i]=len（len表示最长递增序列为多长用二分的lis求的），至于这个点是属于所有的递增序列还

是不是，只要存在j使得dpAfter[i]=dpAfter[j]，那么就是不属于所有的最长递增序列。

 

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int M = 1e5 + 10;
int a[M] , b[M] , a2[M] , b2[M] , dpBefore[M] , dpAfter[M] , flag[M] , cmp[M];
int binsearch(int num , int sta , int end) {
    int l = sta , r = end;
    int mid = (l + r) >> 1;
    while(l <= r) {
        mid = (l + r) >> 1;
        if(b[mid] < num) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}
int binsearch2(int num , int sta , int end) {
    int l = sta , r = end;
    int mid = (l + r) >> 1;
    while(l <= r) {
        mid = (l + r) >> 1;
        if(b2[mid] <= num) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}
int main() {
    int n;
    scanf("%d" , &n);
    memset(cmp , 0 , sizeof(cmp));
    for(int i = 1 ; i <= n ; i++) {
        scanf("%d" , &a[i]);
        a2[i] = a[i];
        flag[i] = 0;
    }
    int len = 1;
    b[len] = a[1];
    for(int i = 2 ; i <= n ; i++) {
        if(a[i] > b[len]) {
            b[++len] = a[i];
            dpBefore[i] = len - 1;
        }
        else {
            int pos = binsearch(a[i] , 1 , len);
            b[pos + 1] = a[i];
            dpBefore[i] = pos;
        }
    }
    int len2 = len;
    b2[len2] = a[n];
    for(int i = n - 1 ; i >= 1 ; i--) {
        if(a[i] < b2[len2]) {
            b2[--len2] = a[i];
            dpAfter[i] = len - len2;
        }
        else {
            int pos = binsearch2(a[i] , len2 , len);
            b2[pos - 1] = a[i];
            dpAfter[i] = len - pos + 1;
        }
    }

    for(int i = 1 ; i <= n ; i++) {
        if(dpBefore[i] + dpAfter[i] == len - 1) {
            flag[i] = 1;
            cmp[dpAfter[i]]++;
        }
    }
    for(int i = 1 ; i <= n ; i++) {
        if(flag[i]) {
            if(cmp[dpAfter[i]] > 1) {
                printf("2");
            }
            else {
                printf("3");
            }
        }
        else {
            printf("1");
        }
    }
    printf("\n");
    return 0;
}