cdq和整体二分之间的关系好迷啊
原题：
佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值
可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你
，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可
。注意：每种变化最多只有一个值发生变化。在样例输入1中，所有的变化是：
1 2 3
2 2 3
1 3 3
1 1 31 2 4
选择子序列为原序列，即在任意一种变化中均为不降子序列在样例输入2中，所有的变化是:3 3 33 2 3选择子序列
为第一个元素和第三个元素，或者第二个元素和第三个元素，均可满足要求
n<=100,000
这题在无上大神犇claris指点下发现是cdq分治，cdq分治这种东西我虽然会但是学的不好，遇到用cdq分治的题总能用(伪)整体二分做
然后这道题似乎不能用整体二分了，至少我的整体二分错了，网上也找不到使用整体二分的题解
所以只能看别人的代码搞cdq分治了，cdq分治的代码非常好懂，这道题很容易就看明白了，但是将思路扩展到更广泛的应用还需要继续思考
所以先说一下此题的思路：
首先先要明确一下题意，每次只能改一个数，如果想改另一个就必须先把这个数变回原来的再改另一个（这个我开始想的一段时间理解错了，看了题解才发现
然后就可以用max[i]表示这个数最大能变成什么，min[i]是最小能变成什么
酱紫就转化成一个近似lis(导弹拦截)的模型，能使f[j]转移到f[i]转移的条件是j<i，max[j]<=a[i]，a[j]<=min[i]，然后这就是个三维偏序的问题
经典cdq分治
先递归l到mid+1处理前半段，然后对前半段的a增序排序，后半段的min增序排序
i从l到mid，在外面定义一个j=mid+1，每次如果min[j]<a[i]，就更新j的答案并j++，在i的循环结束后还要j到r更新剩下的j的答案
感觉好玄啊，其中的奥妙还需要更多的思考
注意不能直接暴力memset树状数组，最好写个一清楚函数，比直接memset快不知道哪里去了
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int rd(){int z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
struct dcd{int x,y,z,id;}a[];
int n,m,b[];
int id[],mx[],mn[];
int f[];
dcd q[];
int ans[];
int e[],lbt[];
void gtlbt(){ for(int i=;i<=n;++i) lbt[i]=i&-i;}
//void mdf(int x,int y){ while(x<=n) e[x]+=y,x+=lbt[x];}
//int qr(int x){ int bwl=0; while(x) bwl+=e[x],x-=lbt[x]; return bwl;}
void mdf(int x,int y){ while(x<=n) e[x]=max(e[x],y),x+=lbt[x];}
void dlt(int x){ while(x<=n) e[x]=,x+=lbt[x];}
int qr(int x){ int bwl=; while(x) bwl=max(bwl,e[x]),x-=lbt[x]; return bwl;}
/*void bnr(int l,int r){
if(l==r) return ;
int md=(l+r)>>1;
*for(int i=l;i<=r;++i){
if(a[i].y>=md) ans[a[i].id]+=qr(a[i].x);
if(a[i].x<=md) mdf(a[i].z,1);
}*
//cout<<md<<endl;
memset(e,0,sizeof(e));
for(int i=l;i<=r;++i){
//cout<<l<<" "<<r<<" "<<a[i].y<<" "<<a[i].x<<" "<<a[i].z<<endl;
if(a[i].y>=md) f[a[i].id]=max(f[a[i].id],qr(a[i].x)+1);
if(a[i].x<=md) mdf(a[i].z,f[a[i].id]);
}
//for(int i=l;i<=r;++i)if(a[i].x<=md) mdf(a[i].z,-1);
int t1=l,t2=md+1;
for(int i=l;i<=r;++i) q[(a[i].y<=md?t1:t2)++]=a[i];
for(int i=l;i<=r;++i) q[i]=q[i];
bnr(l,md),bnr(md+1,r);
}*/
bool cmp1(dcd x,dcd y){ return x.x<y.x;}
bool cmp2(dcd x,dcd y){ return x.y<y.y;}
bool cmp3(dcd x,dcd y){ return x.id<y.id;}
void cdq(int l,int r){
if(l==r) return ;
int md=(l+r)>>;
cdq(l,md);
sort(a+l,a+md+,cmp1),sort(a+md+,a+r+,cmp2);
//memset(e,0,sizeof(e));
int j=md+;
for(int i=l;i<=md;++i){
while(j<=r && a[j].y<a[i].x) ans[a[j].id]=max(ans[a[j].id],qr(a[j].x)+),++j;
mdf(a[i].z,ans[a[i].id]);
}
while(j<=r) ans[a[j].id]=max(ans[a[j].id],qr(a[j].x)+),++j;
for(int i=l;i<=md;++i) dlt(a[i].z);
sort(a+md+,a+r+,cmp3);
cdq(md+,r);
}
int main(){
//freopen("ddd.in","r",stdin);
//freopen("heoi2016_seq.in","r",stdin);
//freopen("heoi2016_seq.out","w",stdout);
memset(f,,sizeof(f));
cin>>n>>m;
gtlbt();
for(int i=;i<=n;++i) mx[i]=mn[i]=b[i]=rd();
int l,r;
while(m--){
l=rd(),r=rd();
mx[l]=max(mx[l],r),mn[l]=min(mn[l],r);
}
for(int i=;i<=n;++i) a[i].id=i,a[i].x=b[i],a[i].y=mn[i],a[i].z=mx[i],ans[i]=;
cdq(,n);
int mxx=;
for(int i=;i<=n;++i) mxx=max(mxx,ans[i]);
cout<<mxx<<endl;
return ;
}