题解 P4093 【[HEOI2016/TJOI2016]序列】

非常传统的一道cdq套dp的题目 如果熟练掌握cdq的话应该可以很快的敲出来？ ## CDQ分治优化dp 先说什么是CDQ 其实cdq就是滚动式的树套树 还记得dp里有一个东西叫滚动数组优化吗？ 滚动数组仅仅优化了空间却没有优化时间复杂度 cdq分治也是如此，相较于树套树，cdq分治并不会节约时间复杂度 相反，cdq分治的特点是省空间，从头到尾只有一个低维数据结构和被分治数组的空间开销，(以及一点系统栈的内存？)，以及比树套树少的常数和代码量 为什么cdq可以部分的替代树套树呢？ **因为cdq分治那个solve函数的本质是树套树外层树的中序遍历函数** 换句话来讲，如果我们只是需要树套树外层树的中序遍历函数的话，我们就可以使用cdq分治，在时间维度而不是在空间维度上生成这个树套树的外层部分，从而隐性的使用了一个树套树 那么下面我们以这个题为例讲解下CDQ分治的正确姿势吧(其实也不一定正确) 首先由于这道题本质上还是一个dp所以请先让我们推一发转移方程 令$Dp_{i}$以i为结尾的最长上升子序列长度(允许其中一个元素任意变换) 那么为了求$Dp_{i}$我们枚举上一个点是谁 所以大概长这样？ ## $Dp_{i}=max(Dp_{j})+1$ 中j同时满足下面3个限制 1.$j<=i$ 2.$val_{j}<=min_{i}$ 3.$max_{j}<=val_{i}$ 后两个限制条件是我们枚举i和j那个变化之后产生的结果 (max和min表示的是一个元素可以变化的最大值和最小值) 那么我们发现max运算是允许乱序的 也就是说，只要你为每一个i求出了一个所有合法的j集合，就可以转移 至于求这个集合的过程，是随便的，你想怎么求就怎么求 那么我们现在只是处理l，r这一段区间的转移关系，假设我们使用了一些奥妙重重的手法使得l以前的dp值全部被求出并且也向l，r区间的点进行了转移 **我们希望望这个solve函数结束时，l,r内的dp值全部被求出** _(显然在只有一个点的时候这个点的dp值已经被求出可以直接return)_ 所以我们现在只需要**考虑l，r之间点的转移关系**就行了 此时我们人为的将这个区间分为两半，同时我们递归的调用这个函数solve(l,mid) 这样因为我们调用了一次solve函数，所以l,mid之间的点已经被求出了 此时我们只考虑l,mid对mid，r之间的转移关系 发现**l，mid的下标全部小于mid，r之间的下标**，所以这一维的限制不存在了 所以我们把l，mid按val值排序，把mid，r按min值排序 此时我们枚举我们要要用l，mid中的点转移mid，r中的某一个点i 现在要使用一些奇技淫巧来消掉剩下的两位限制了 发现l,mid中可以转移到i的点，在按val排序之后是一个连续前缀，假设这是以j为结尾的前缀 此时我们发现j之前的点的val值全部小于等于i的min，所以第二维限制也不存在了 下面我们考虑第三维限制，发现是$max_{j}<=val_{i}$因此我们可以将j之前的所有点p都将各自的dp值插入到树状数组的$max_{p}$位置上，此时我们只需要查一发前缀最大值和i当前的dp值取个max就可以完成在l,mid范围内的转移了 由于我们发现i是按$min_{i}$排序的，所以我们可以保证j指针不会后退，树状数组里也不会删除点，因此我们的总复杂度是$O(LenlogLen)$的 但是我们并不可以就此返回，因为此时l，r内的dp值并没求完，但是l，mid内的值已经求好了，而且也向mid，r完成了转移，所以满足我们使用solve(mid，r)的条件了，此时我们可以使用一次solve(mid，r)来讲mid到r范围内的dp值求出 此时我们已经求出了l，r内的全部dp值，所以我们可以return了 如果你足够熟练的话很容易的就可以看出上述算法实际上就是对着dp值建了一棵线段树然后跑了一遍线段树的中序遍历然后动态的保存了下每个区间的dp值结果 我们solve函数其实就是考虑了线段树上3个节点的关系(l,r)(l,mid)(r,mid) 同时在每个solve函数结束的时刻，这个dp数组实际上存储了线段树这个节点的全部信息 所以我们最后要做的事就是调用一次solve(0,n)函数，求出最大的dp值而已 ~~(废了那么多话其实代码只有50行)~~ 上代码~ ``` #include<cstdio> #include<algorithm> using namespace std;const int N=1e5+10; struct nod{int val;int mi;int ma;int pos;int dp;}a[N];int n;int m;int res=1; inline bool cmp1(const nod& a,const nod& b){return a.val<b.val;}//3个比较函数 inline bool cmp2(const nod& a,const nod& b){return a.mi<b.mi;} inline bool cmp3(const nod& a,const nod& b){return a.pos<b.pos;} struct data//离散化 { int v;int fr;int tp; friend bool operator <(data a,data b){return a.v<b.v;} friend bool operator ==(data a,data b){return a.v==b.v;} }l[3*N];int rk[3*N];int ct; struct trearray//树状数组 { int ta[3*N]; inline void c(int x,int c){for(;x<=3*n;x+=x&(-x)){ta[x]=max(ta[x],c);}} inline void d(int x){for(;x<=3*n;x+=x&(-x)){ta[x]=0;}} inline int q(int x){int r=0;for(;x>0;x-=x&(-x)){r=max(r,ta[x]);}return r;} }ta; void solve(int l,int r)//solve函数 { if(r-l==1){return;}int mid=(l+r)/2; solve(l,mid);sort(a+l+1,a+mid+1,cmp1);sort(a+mid+1,a+r+1,cmp2); for(int i=mid+1,j=l+1;i<=r;i++)//双指针+树状数组转移 {for(;a[j].val<=a[i].mi&&j<=mid;j++){ta.c(a[j].ma,a[j].dp);}a[i].dp=max(a[i].dp,ta.q(a[i].val)+1);} for(int i=l+1;i<=mid;i++){ta.d(a[i].ma);}sort(a+mid+1,a+r+1,cmp3);solve(mid,r);//最后别忘了把mid到r恢复下 } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){int t;scanf("%d",&t);a[i]=(nod){t,t,t,i,0};} for(int i=1;i<=m;i++) {int x;int t;scanf("%d%d",&x,&t);a[x].mi=min(a[x].mi,t);a[x].ma=max(a[x].ma,t);} for(int i=1;i<=n;i++)//离散化 {l[++ct]=(data){a[i].val,i,0};l[++ct]=(data){a[i].mi,i,1};l[++ct]=(data){a[i].ma,i,2};} sort(l+1,l+3*n+1);rk[1]=1; for(int i=2;i<=3*n;i++){rk[i]=(l[i]==l[i-1])?rk[i-1]:i;} for(int i=1;i<=3*n;i++) { switch(l[i].tp) { case 0:{a[l[i].fr].val=rk[i];break;} case 1:{a[l[i].fr].mi=rk[i];break;} case 2:{a[l[i].fr].ma=rk[i];break;} } }a[1].dp=1;solve(0,n);//然后solve(0,n)就好了 for(int i=1;i<=n;i++){res=max(res,a[i].dp);} printf("%d",res);return 0;//拜拜程序~ } ```