题意：
给出n段区间[li,ri]；
求一个最长的连续区间串，满足存在一个不降序列Ai，且Ai∈[li,ri]；
1<=n<=1000000；
题解：
感觉Poi题越来越难了。。。这sb题都错成狗。。
我眼一花把范围看成了10W，然后YY了一个线段树；
用线段树来维护所有点的DP值，然后直接DP乱搞；
时间复杂度O(nlogn)，空间复杂度O(nlogn)；
然后我调了一下午，发现T了；
之后我离散化了一下，又调了很久。。发现是RE！
再看到数据范围100W的时候我的内心是吐血的；
于是我调完了线段树自己跑了一遍数据，130秒，125MB内存；
很好，常数的问题而已这题精神AC吧
于是我去查了优越的O(n)正解；
正解是用了一个单调队列，，来维护哪些区间是合法的；
维护一个单调不增的l端点；
将l大于当前r的队首元素弹掉，更新目前序列的左端点；
然后插入当前元素，更新答案；
这样就可以O(n)啦，想想刚才的我真是sb；
代码：
非常优雅的正解：
#include<stdio.h>#define N 1100000int l[N],r[N],q[N],st,en;int main(){int n,i,ans,top;scanf("%d",&n);st=1,en=0,top=1;for(i=1,ans=0;i<=n;i++){scanf("%d%d",l+i,r+i);while(st<=en&&r[i]<l[q[st]])top=q[st++]+1;while(st<=en&&l[q[en]]<=l[i])en–;q[++en]=i;ans=ans>i-top+1?ans:i-top+1;}printf("%d",ans);}又长又逗比既MLE还TLE的线段树：
#include<stdio.h>#include<string.h>#include<algorithm>#define N 1100000#define lson l,mid,no<<1#define rson mid+1,r,no<<1|1using namespace std;int l[N],r[N];int dis[N<<1];int ma[N<<3],cova[N<<3],covc[N<<3];bool cov0[N<<3];void Pushup(int no){ma[no]=max(ma[no<<1],ma[no<<1|1]);}void Pushdown(int no){if(cov0[no]==1){ma[no<<1]=0;cova[no<<1]=0;covc[no<<1]=-1;ma[no<<1|1]=0;cova[no<<1|1]=0;covc[no<<1|1]=-1;cov0[no<<1]=cov0[no<<1|1]=1;cov0[no]=0;return ;}if(cova[no]){if(cov0[no<<1])Pushdown(no<<1);if(cov0[no<<1|1])Pushdown(no<<1|1);cov0[no<<1]=0;cov0[no<<1|1]=0;cova[no<<1]+=cova[no];cova[no<<1|1]+=cova[no];if(covc[no<<1]!=-1)covc[no<<1]+=cova[no];if(covc[no<<1|1]!=-1)covc[no<<1|1]+=cova[no];ma[no<<1]+=cova[no];ma[no<<1|1]+=cova[no];cova[no]=0;}if(covc[no]!=-1){if(cov0[no<<1])Pushdown(no<<1);if(cov0[no<<1|1])Pushdown(no<<1|1);cov0[no<<1]=0;cov0[no<<1|1]=0;covc[no<<1]=max(covc[no<<1],covc[no]);covc[no<<1|1]=max(covc[no<<1|1],covc[no]);ma[no<<1]=max(ma[no<<1],covc[no]);ma[no<<1|1]=max(ma[no<<1|1],covc[no]);covc[no]=-1;}}void clear(int l,int r,int no,int st,int en){if(st<=l&&r<=en){ma[no]=0;cova[no]=0;covc[no]=-1;cov0[no]=1;}else{Pushdown(no);int mid=l+r>>1;if(en<=mid)clear(lson,st,en);else if(st>mid)clear(rson,st,en);elseclear(lson,st,en),clear(rson,st,en);Pushup(no);}}void update(int l,int r,int no,int st,int en,int val){if(st<=l&&r<=en){if(cov0[no])Pushdown(no);ma[no]=max(ma[no],val);covc[no]=max(covc[no],val);cov0[no]=0;}else{Pushdown(no);int mid=l+r>>1;if(en<=mid)update(lson,st,en,val);else if(st>mid)update(rson,st,en,val);elseupdate(lson,st,en,val),update(rson,st,en,val);Pushup(no);}}void add(int l,int r,int no,int st,int en){if(st<=l&&r<=en){if(cov0[no])Pushdown(no);ma[no]++;if(cova[no]!=-1)cova[no]++;covc[no]++;cov0[no]=0;}else{Pushdown(no);int mid=l+r>>1;if(en<=mid)add(lson,st,en);else if(st>mid)add(rson,st,en);elseadd(lson,st,en),add(rson,st,en);Pushup(no);}}int main(){int n,i,j,k,tl,tr,len,lastr,ans;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",l+i,r+i);dis[i+i-1]=l[i];dis[i+i]=r[i];}sort(dis+1,dis+n+n+1);len=unique(dis+1,dis+n+n+1)-dis-1;memset(covc,-1,sizeof(covc));for(i=1,ans=0,lastr=len+1;i<=n;i++){tl=lower_bound(dis+1,dis+len+1,l[i])-dis;tr=lower_bound(dis+1,dis+len+1,r[i])-dis;if(lastr<=tr&&lastr!=len)update(1,len,1,lastr+1,len,ma[1]);add(1,len,1,tl,tr);if(tl!=1)clear(1,len,1,1,tl-1);if(tr!=len)clear(1,len,1,tr+1,len);ans=max(ans,ma[1]);lastr=tr;}printf("%d\n",ans);return 0;}
哪怕前方的路会充满坎坷，但为梦想而拼搏的人会永不言败
