https://www.lydsy.com/JudgeOnline/problem.php?id=4553
佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可。注意：每种变化最多只有一个值发生变化。在样例输入1中，所有的变化是：
1 2 32 2 31 3 31 1 31 2 4选择子序列为原序列，即在任意一种变化中均为不降子序列
一道比较难的题？可能是我CDQ很久没写的缘故了……
设l[i]~r[i]表示i数的变动范围，考虑f[i]=max(f[j])+1，其中j要满足：
j<i
a[j]<=l[i]
r[j]<=a[i]
很显然是CDQ三维（？）偏序的模型，但是有四个变量，所以归并排序貌似不可做……
改一下变量名变成：
tj<ti
xj<=yi
zj<=xi
我们一维排t，二维mid左右两边分别排x和y，然后按照顺序类似归并排序把两边的x和y合在一起，再用树状数组维护第三维就好啦！
当然注意每次我们处理完别忘了要回归原位！
#include<map> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<cctype> #include<vector> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=1e5+5; const int MAX=1e5; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch==‘-‘;ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } struct node{ int x,y,z,t,ans; }a[N]; int n,m,tr[N]; inline int lowbit(int x){return x&(-x);} inline void add(int x,int y){ for(int i=x;i<=MAX;i+=lowbit(i))tr[i]=max(tr[i],y); } inline int query(int x){ int res=0; for(int i=x;i;i-=lowbit(i))res=max(res,tr[i]); return res; } inline void mdy(int x){ for(int i=x;i<=MAX;i+=lowbit(i))tr[i]=0; } inline bool cmpt(node a,node b){ return a.t<b.t; } inline bool cmpx(node a,node b){ return a.x==b.x?a.t<b.t:a.x<b.x; } inline bool cmpy(node a,node b){ return a.y==b.y?a.t<b.t:a.y<b.y; } void cdq(int l,int r){ if(l>=r)return; int mid=(l+r)>>1; cdq(l,mid); sort(a+l,a+mid+1,cmpx); sort(a+mid+1,a+r+1,cmpy); for(int i=l,j=l,k=mid+1;i<=r;i++){ if(j<=mid&&(k>r||a[j].x<=a[k].y))add(a[j].z,a[j].ans),j++; else a[k].ans=max(a[k].ans,query(a[k].x)+1),k++; } for(int i=l;i<=mid;i++)mdy(a[i].z); sort(a+mid+1,a+r+1,cmpt); cdq(mid+1,r); } int main(){ n=read(),m=read(); for(int i=1;i<=n;i++)a[i].x=a[i].y=a[i].z=read(),a[i].t=i; for(int i=1;i<=m;i++){ int x=read(),y=read(); a[x].y=min(a[x].y,y); a[x].z=max(a[x].z,y); } for(int i=1;i<=n;i++)a[i].ans=1; cdq(1,n); int ans=0; for(int i=1;i<=n;i++)ans=max(ans,a[i].ans); printf("%d\n",ans); return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
BZOJ4553：[HEOI2016/TJOI2016]序列——题解
原文：https://www.cnblogs.com/luyouqi233/p/9189854.html