一、解决偏序问题
不言即默认非严格偏序问题。
严格偏序，未有此题。
若汝要学，小点三维。
同 \(a\) 者并，\(b\) \(c\) 小改。
幸甚至哉，歌以咏志。
三维偏序
按第一维排序，通过只计算左对右造成的贡献来满足第一维偏序条件。
第二维对于左右两个区间分别独自按第二维排序然后双指针，满足第二维偏序条件。
第三维用权值树状数组的位置，并用前缀和形式解决第三维偏序条件并顺便统计答案。
多维偏序
k 维偏序可用 \(CDQ^{k-2}\) 解决，复杂度 \(O(n\ \log^{k-1}\ n)\)。
以四维偏序为例：
\(\operatorname{cdq1}(l,r)\)：
先按 \(a\) 排序
把 \([l,mid]\) 的 \((a,b,c,d)\) 变成 \((0,b,c,d)\)
把 \([mid+1,r]\) 的 \((a,b,c,d)\) 变成 \((1,b,c,d)\)
然后令 \(\operatorname{cdq2}(l,r)\) 中只能 \(0\) 对 \(1\) 造成贡献，一 \(ok！\)
然后以 \(b\) 为第一关键字排序，令 \(\operatorname{cdq2}(l,r)\) 中只能 \([l,mid]\) 对 \([mid+1,r]\) 造成贡献，二 \(ok！\)
\(\operatorname{cdq2}(l,r)\)：
按 \(c\) 排序 + 双指针，三 \(ok！\)
按 \(d\) 插入权值树状数组，四 \(ok！\)
问：那我问你那我问你，多维偏序就这样一直给前几维附 0、1，那我三维偏序为啥写单调队列和树状数组？
三维偏序——去单调队列 \(O(n\ \log\ n \ \log \ k)\)
三维偏序——CDQ 套 CDQ \(O(n\ \log^2\ n)\)
注：普通三维偏序是 \(O(n\ \log\ n \ \log \ k)\)。
答：因为写的人多，你可以选择你的御用写法。
注意 5 维偏序就已经是恐怖的 \(O(n \log^4n)\) 了！
苦心哥天不负，四个老哥可吞吾。
二、优化 1D DP
小说
1D DP：状态数为 \(O(n)\) ，一次转移为 \(O(n)\)。
显然这种 DP 暴力是 \(O(n^2)\)，有时可以用 CDQ 降到 \(O(n \ \log^{k-1} \ n)\) （\(k\) 维偏序）。
中说
一般 CDQ 优化的 DP 转移形似偏序，\(k\) 维偏序也可以优化 DP。
例如：二维最长上升子序列。
此时转移式子形似三维偏序（\(i\)、\(a_i\)、\(b_i\)）。
关于 DP 值我们可以想办法在树状数组上解决。
此时我们注意要先 cdq(1,mid),sort(l,mid,cmp2),sort(mid+1,r,cmp2),solve(l,r) 再 sort(mid+1,r,cmp1),cdq(mid+1,r)。
反证：假设 \(l<mid+1\le k<j\le r\)，\(f_j\) 先在 \([mid+1,r]\) 更新，再在 \([l,mid]\) 更新，\(f_j\) 在 \([mid+1,r]\) 里用来更新的 \(f_k\) 不是 \(f_k\) 最终的值，证毕。
小综上——附四维偏序优化 1D DP 码：
bool cmp1(xxx x,xxx y) {return (x.a==y.a)?((x.b==y.b)?((x.c==y.c)?(x.d<y.d):(x.c<y.c)):(x.b<y.b)):(x.a<y.a);}
bool cmp2(xxx x,xxx y) {return (x.b==y.b)?((x.c==y.c)?((x.d==y.d)?(x.a<y.a):(x.d<y.d)):(x.c<y.c)):(x.b<y.b);}
bool cmp3(xxx a,xxx b) {return (a.c==b.c?a.d<b.d:a.c<b.c);}
void cdq2(int l,int r)
{if(l==r) return ;int mid=(l+r)>>1;cdq2(l,mid),sort(d+l,d+mid+1,cmp3),sort(d+mid+1,d+r+1,cmp3);int i=l;for(int j=mid+1;j<=r;j++){while(d[i].c<=d[j].c&&i<=mid) ((!d[i].ok)?gai(d[i].d,d[i].ans):void()),i++;if(d[j].ok) d[j].ans=max(d[j].ans,cha(d[j].d)+d[j].cnt);}qing(l,i-1),sort(d+l,d+r+1,cmp2),cdq2(mid+1,r);
}
void cdq1(int l,int r)
{if(l==r) return ;int mid=(l+r)>>1;cdq1(l,mid);for(int i=l;i<=mid;i++) d[i].ok=0;for(int i=mid+1;i<=r;i++) d[i].ok=1;sort(d+l,d+r+1,cmp2),cdq2(l,r),sort(d+l,d+r+1,cmp1),cdq1(mid+1,r);
}
\(甄雨村\)
主要特征：将 \(2^i\) 形区间打包给后面的 dp 数组转移。
三、斜率优化套 CDQ
快进到 \(y=kx+b\) 表示后：
这种斜率优化在转移 \(f_i\) 时总有 \(j<i\) 的限制，因为这会让 \(i\) 的增长很重要，进而让 \(x\) 与 \(k\) 数组的单调性很重要：
（以下为均摊）
如果 \(x\) 单调，那么单调队列轻松 \(O(1)\) 维护凸包。
如果 \(k\) 单调，那么单调队列轻松 \(O(1)\) 找决策点。
如果 \(k\) 不单调，那么可以单调队列上二分劳累 \(O(log)\) 找决策点。
如果 \(x、k\) 不单调，那么可以平衡树独立（指没人帮你调）解决。
紫雾翻涌间，CDQ 踏着虚空符文缓步而出，黑袍无风自动，斗篷下摆流淌着液态的夜，跃动的分治形成绝对领域……
曰：“ \(x、k\) 不单调？蝼蚁……”
只用计算 \([l,mid]\) 对 \([mid+1,r]\) 的贡献，维护 \([l,mid]\) 的凸包，在 \([mid+1,r]\) 上找决策点。
对 \([l,mid]\) 按 \(x\) 排序，对 \([mid+1,r]\) 按 \(k\) 排序。
（至于代码里为什么要先按 id 排序，这是 CDQ DP 必带的，因为第一维被打乱了）
注意
-
实时修改询问可以把时间做一维。
-
最后一维要放在权值树状数组里，所以有时要离散化最后一维。
-
如果有重点要去重，原因是重点之间各有贡献，所以应不分先后，对此合并处理。（如果时间作为一维，那么肯定无重点）
-
以三维偏序为例，如果先
cdq(1,mid),sort(l,mid,cmp2),sort(mid+1,r,cmp2),solve(l,r)再sort(mid+1,r,cmp1),cdq(mid+1,r)，注意最后一个sort(mid+1,r,cmp1)必加，否则在左对右时满足不了第一维偏序条件。（当然如果你勤劳，可以拿一个数组存下上次按 \(\operatorname{cmp1}\) 排好序的数组，就可以少 \(\operatorname{sort}\) 几次——常数优化）。
