好久不动题目了，今天动了一题，忒背运，死都TLE，想了想，算法复杂度没问题啊，n=100000，nlogn的算法拼1S的RP咋崩溃的。。后来想起了无敌的POJ超级慢速set，无奈，不想改，到处搜有这题的OJ，TOJ上跑了下，10MS。。汗。。下载数据数据来看了看，就是12组，就是本地debug也不会TLE啊。。没办法。。
不发牢骚了，说说这题的方法吧。
一般的最长递增字串用n^2做很好做，就是dp[i]=max{dp[j]+1,height[j]<height[i]}，这题可以用单调队列做优化，但是和普通的单调队列不同，要借助平衡树
首先，我们知道，要维护这样一个单调队列，当height[i]<height[j]时，要有dp[i]<dp[j]，否则的话，status{(j,height[j])}这个状态以后不会推得最优解，可以删除。这题麻烦就麻烦再height不是个单调的函数，随着i的增大（就是沿着DP方向计算）时，height不能保证也是递增的，木有办法，只能维护一个平衡树那样的东西。
那么更新过的DP方程就是
dp[i]=dp[j]+1,j为满足height[j]<height[i]的最后一个元素
然后更新单调队列的策略是把当前决策加入单调队列里，然后往后删除dp[i]>=dp[j]并且height[i]<height[j]的statue{j}。
每个元素最多入队一次，出队一次，所以总得复杂度o(nlogn)
我是全部用set实现的，轻松好省
1 # include <cstdio>
2 # include <
set>
3 using namespace std;
4 struct node
5 {
6 int height,id;
7 node(
int h,
int i):height(h),id(i){}
8 bool operator<(
const node &pos)
const 9 {
10 if(height!=pos.height)
return height<pos.height;
11 else return id<pos.id;
12 }
13 };
14 set<node> q;
15 int dp[100005];
16 int main()
17 {
18 int n;
19 while(scanf("%d",&n)!=EOF)
20 {
21 q.clear();
22 for(
int i=0;i<n;i++)
23 {
24 int t;
25 scanf("%d",&t);
26 set<node>::iterator it=q.lower_bound(node(t,-1));
27 int ans;
28 if(it==q.begin())
29 ans=1;
30 else31 ans=dp[(--it)->id]+1;
32 it=q.lower_bound(node(t,-1));
33 if(it!=q.end()&&it->height==t)
34 it=q.erase(it);
35 while(it!=q.end()&&dp[it->id]<=ans)
36 it=q.erase(it);
37 q.insert(node(t,i));
38 dp[i]=ans;
39 }
40 printf("%d\n",dp[q.rbegin()->id]);
41 }
42 return 0;
43 }
44