题目链接：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;
}