cdq(陈丹琦)分治, 是一种类似二分的算法. 基本思想同分治:
递归, 把大问题划分成若干个结构相同的子问题, 直到(L==R);
处理左区间 [L,mid] 对右区间 [mid+1,R] 的影响;
合并.
它可以顶替复杂的高级数据结构, 但必须离线操作.
N 维偏序, 就是求 N 个关键字下的顺 / 逆序对. cdq 分治是这类题中常用的降维手段.
一维偏序
学习归并排序时, 我们了解到它的一个特性就是可以用来求逆序对.
Luogu P1908 逆序对
- void merge(int L,int R) {
- if(L == R)return;
- int mid = (L+R)/2;
- merge(L,mid);
- merge(mid+1,R);
- int idx = L;
- int i = L,j = mid+1;
- while(i <= mid&&j <= R) {
- if(a[i] <= a[j])temp[idx++] = a[i++];
- else {
- temp[idx++] = a[j++];
- cnt += mid-i+1;
- }
- }
- while(i <= mid)temp[idx++] = a[i++];
- while(j <= R)temp[idx++] = a[j++];
- for(int i = L; i <= R; i++)
- a[i] = temp[i];
- }
归并排序求逆序对
考虑它的原理: 只统计对于右面的每一个元素, 左边比它大的.
两边的数列都为有序, 且各自的逆序对都已经统计完了.
那么对于右边的第 j 个元素(j>=mid+1), 如果左边的第 i 个元素比 j 大, 那么 i+1,i+2.... 到 mid 一定都比 j 大.
这里就体现了 cdq 分治的思想, 也是多维偏序的基础. 可以说, 归并排序求逆序对是 cdq 分治的一个特例.
二维偏序
除了归并排序, 一维偏序也可以用树状数组解决. 实际上, 一部分树状数组能解决的问题, cdq 分治也可以解决.
Luogu P3374 [模板] 树状数组 1
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #define MogeKo qwq
- using namespace std;
- const int maxn = 500005;
- int n,m,opt,x,y,sum[maxn];
- int lowbit(int x){
- return x & -x;
- }
- void update(int x,int k){
- while(x <= n){
- sum[x] += k;
- x += lowbit(x);
- }
- }
- int query(int x){
- int ans = 0;
- while(x){
- ans += sum[x];
- x -= lowbit(x);
- }
- return ans;
- }
- int main(){
- scanf("%d%d",&n,&m);
- for(int i = 1;i <= n;i++){
- scanf("%d",&y);
- update(i,y);
- }
- for(int i = 1;i <= m;i++){
- scanf("%d%d%d",&opt,&x,&y);
- if(opt == 1)update(x,y);
- if(opt == 2)printf("%d\n",query(y)-query(x-1));
- }
- return 0;
- }
树状数组
树状数组板子题, 可以轻松解决.
把它转化为二维偏序问题, 对于每个修改和询问, 都有 (时间, 位置) 两个维度.
开一个结构体 q[], 数组下标记录时间, q[].id 记录位置, q[].type 记录类型(修改或询问). 注意, 当修改和询问在同一位置时, 修改操作要优先.
解决二维偏序问题首先需要控制一维有序, 另一维进行归并排序. 在这里, 时间默认就是有序的(++cnt);
对于每个修改操作, 记录修改的元素位置. 数组赋初值的方式和修改操作相同, 可以当做时间在最前的修改.
查询怎么办? 用树状数组求一段区间和时, 需要用到前缀和, 即 R-(L-1).
那么, 询问的位置也可以拆分成两个:(L-1)和 R. 用不同的 type 来区分它们:( L-1 的要减去, R 的要加上).
如何进行归并排序? 对于一段位置有序的区间, 一定是时间在前的修改操作会影响时间在后的查询操作.
用 sum 维护区间内修改操作的值, 修改时用 sum + 修改值;
用 ans 记录询问的答案, ans - 所有 (L-1) 的 sum + 所有 R 的 sum 即为这个询问的结果. 为啥非要用 cdq 分治啊麻烦死了 QAQ!!!
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #define MogeKo qwq
- using namespace std;
- const int maxn = 500005*3;
- int n,m,cnt,cqry,opt,x,y,ans[maxn];
- struct node{
- int type,id,val;
- bool operator <(const node & x) const{
- if(id != x.id)return id < x.id;
- else return type < x.type;
- }
- }q[maxn],tem[maxn];
- void cdq(int L,int R){
- if(L == R) return;
- int mid = L+R>>1;
- cdq(L,mid),cdq(mid+1,R);
- int t1 = L,t2 = mid+1;
- int sum = 0;
- for(int i = L;i <= R;i++){
- if( (t1 <= mid && q[t1]<q[t2]) || t2> R){
- if(q[t1].type == 1) sum += q[t1].val;
- tem[i] = q[t1++];
- }
- else{
- if(q[t2].type == 2) ans[q[t2].val] -= sum;
- if(q[t2].type == 3) ans[q[t2].val] += sum;
- tem[i] = q[t2++];
- }
- }
- for(int i = L;i <= R;i++) q[i] = tem[i];
- }
- int main(){
- scanf("%d%d",&n,&m);
- for(int i = 1;i <= n;i++){
- cnt++;
- scanf("%d",&y);
- q[cnt].type = 1;
- q[cnt].id = i;
- q[cnt].val = y;
- }
- for(int i = 1;i <= m;i++){
- scanf("%d%d%d",&opt,&x,&y);
- if(opt == 1){
- q[++cnt].type = 1;
- q[cnt].id = x;
- q[cnt].val = y;
- }
- if(opt == 2){
- cqry++;
- q[++cnt].type = 2;
- q[cnt].id = x-1;
- q[cnt].val = cqry;
- q[++cnt].type = 3;
- q[cnt].id = y;
- q[cnt].val = cqry;
- }
- }
- cdq(1,cnt);
- for(int i = 1;i <= cqry;i++)
- printf("%d\n",ans[i]);
- return 0;
- }
二维偏序
三维偏序
Luogu P3810 [模板] 三维偏序(陌上花开)
扩展到三维. 设三维分别为 x,y,z
先按 x 排序, 消除第一维的影响.
考虑不使用 cdq, 用一个树状数组维护第二维, 另一个树状数组维护第三维... 就会出现树套树的神奇情况
模仿之前的做法, 第二维使用 cdq 分治, 按 y 进行归并排序. 虽然 x 的顺序被打乱了, 但左一半一定小于右一半. 第二维的影响被消除了.
第三维可以用一个权值树状数组维护.
- int t1=L, t2=mid+1;
- while(t2 <= R){
- while(t1 <= mid && b[t1].y <= b[t2].y){
- tree.update(b[t1].z,b[t1].num);
- t1++;
- }
- b[t2].ans += tree.query(b[t2].z);
- t2++;
- }
已经控制 x2>x1, 将所有 y1<y2 时按 z1 把当前花的个数加入树状数组, 再查询比 z2 小的在树状数组中有多少个.
由于归并排序时, y2 后的 y3 一定大于 y1, 所以已经加入的 z 的个数不用清空.
当归并的操作结束时, 再把树状数组减去已经加入的左区间的 z 的个数(也就是左区间指针 t1 之前).
提供的数据中, 可能有 xyz 完全相同的情况, 所以初始化时要先去重, 但不能直接调用 unique 函数. 统计相同的花的个数, 用结构体的. num 记录.
这样当把花按 x 加入树状数组时, 加入. num 中的个数就可以了.
三维偏序
其实 cdq 分治我也不是很明白 qwq
理论上, cdq 分治可以解决任意 N 维偏序问题. 但是, cdq 套 cdq 的复杂度会达到 n logkn, 当它超过 n2 的时候... 还是选择暴力枚举吧 w
来源: http://www.bubuko.com/infodetail-2972007.html