题意： 一个序列可能有多个最长子序列，现在问每个元素是以下三个种类的哪一类：
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 > ) {
c[x] = max(c[x],val);
x -= lowbit(x);
}
}
}
int getmax(int up,int x) {
int maxi = ;
if(up) {
while(x > ) {
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 = ;
for(i=;i<=n;i++) cin>>a[i], S += "", MAX = max(MAX,a[i]);
memset(c,,sizeof(c));
int LIS = ;
for(i=;i<=n;i++) {
int maxi = getmax(,a[i]-);
dp1[i] = maxi+;
LIS = max(LIS,dp1[i]);
modify(,a[i],dp1[i]);
}
memset(c,,sizeof(c));
for(i=n;i>=;i--) {
int maxi = getmax(,a[i]+);
dp2[i] = maxi+;
modify(,a[i],dp2[i]);
}
mp.clear();
for(i=;i<=n;i++) {
if(dp1[i] + dp2[i] - != LIS) S[i] = '';
else mp[dp1[i]]++;
}
for(i=;i<=n;i++)
if(S[i] != '' && mp[dp1[i]] == ) S[i] = '';
for(i=;i<=n;i++)
if(S[i] == '') S[i] = '';
cout<<S.substr(,n)<<endl;
}
return ;
}