CDQ分治初识_牛客博客

又是一个以前没接触过的东西我要疯啦。

概述

CDQ分治被称为用时间（logn）降维的算法，

与普通分治简单将问题分为一个个独立的子问题不同，

CDQ分治中，每一次划分出来的两个子问题，前一个子问题用来解决后一个子问题，而不是其本身，

即每次计算左区间对右区间的贡献，并从小区间一步步回溯到大区间解决问题（使用归并排序整合小区间）。

要求离线并且存在偏序关系

基本步骤

分。大区间分为长度相等小区间
治。递归处理左区间
治。计算左区间的修改操作对右区间的查询操作的贡献值
治。递归处理右区间
并。归并排序优化（这里不太懂

学到目前箬蒻的一些理解

如图，cdq分治主要思想即在计算左区间对右区间的贡献，以及将离线修改查询转化为偏序问题。

如：给一列数a1,a2,…,an，求它的逆序对数，即有多少个有序对(i,j)，使得i<j但ai>aj。1<=n<=1e6;

1.寻找偏序关系

这就是一个二维偏序问题，对每个i存在ai(下标)，bi(数值)，

问满足ai<aj,bi>bj的（i,j）有多少，一维为下标（因为这维已经有序了所以不必考虑），二维为数值。

2.如何计算贡献值

进行到基本步骤3时，此区间对应的左右小区间都是有序的，

那么若是a[i]>a[j]（a[i]为左区间里的一个数，a[j]为右区间的一个数），

那么左区间对右区间中a[j]位置的总贡献即为mid-i+1。

附菊苣代码（https://blog.csdn.net/K_R_forever/article/details/81702934）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+9;
int a[maxn],b[maxn],ans=0;
void CDQ(int l,int r,int *a)
{
	if(l==r)return;
	int m=(l+r)>>1;
	CDQ(l,m,a);
	CDQ(m+1,r,a);
	int t1=l,t2=m+1;
	for(int i=l;i<=r;i++)
        {
		if(a[t1]>a[t2]&&t2<=r||t1>m)
                {
			b[i]=a[t2++];
			ans+=m-t1+1;
		}
		else
			b[i]=a[t1++];
	}
	for(int i=l;i<=r;i++) a[i]=b[i];
}
int main()
{
	int i,j,k,n;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	CDQ(1,n,a);
	cout<<ans<<endl;
}

理解不够题来凑

A - Tree 园丁的烦恼

VJ链接：https://vjudge.net/contest/316676#problem/A

转化为三维偏序，对每一个三元组（a,b,c）（a为时间，b,c为坐标）
求满足
a0<a
b0<b
c0<c
的更新操作总个数
但是该问题中其实只有二维，因为查询操作中没有穿插更新操作，
时间这一维不用处理（查询总是在更新（初始化数组）后）

作为一个二维偏序问题，其实只需要对X坐标排序，然后对Y坐标用树状数组或cdq分治统计即可。

//#include <bits/stdc++.h>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=5e6+10;
#define pi  acos(-1.0)
#define INF  0x3f3f3f3f
#define mod   1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define lowbit(x)  ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n,m,tot;
struct IN
{
    int x,y,op,k,id,ans;
    //坐标，操作类型,加还是减，
    //出现时间(此时时间前后对答案已经没有影响了)
    //记录时间只是为了找到每个累加值对应的询问
    //目前的累加值。
    friend bool operator <(IN a,IN b)
    {
        if(a.x!=b.x) return a.x<b.x;
        else if(a.y!=b.y) return a.y<b.y;
        return a.op<b.op;//有点先加点嘛
    }
}a[MAXN],b[MAXN];
int ans[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,p=l,cnt=0;
    while(t2<=r)
    {
        while(a[t1].y<=a[t2].y&&t1<=mid)
        {
            if(a[t1].op==1) cnt++;//记录左区间的值对右区间的贡献
            b[p++]=a[t1++];
        }
        if(a[t2].op==2) a[t2].ans+=cnt;//对前面每个左区间影响到的右区间累加
        b[p++]=a[t2++];
    }
    //此时只可能左右区间中的一个还有值
    //左区间未空说明剩下的值全部大于右区间，对右区间无贡献
    //右区间同理
    while(t1<=mid) b[p++]=a[t1++];
    while(t2<=r) b[p++]=a[t2++];
    for(int i=l;i<=r;++i) a[i]=b[i];//归并
}
int main()
{
    while(~s2(n,m))
    {
        tot=0;
        for(int i=1,x,y;i<=n;i++)
        {
            s2(x,y);
            a[++tot]=IN{x,y,1,0,0,0};
        }
        for(int i=1,aa,b,c,d;i<=m;i++)
        {
            scanf("%d %d %d %d",&aa,&b,&c,&d);
            a[++tot]=(IN){c,d,2,1,i,0};
            a[++tot]=(IN){aa-1,b-1,2,1,i,0};
            a[++tot]=(IN){aa-1,d,2,-1,i,0};
            a[++tot]=(IN){c,b-1,2,-1,i,0};
        }
        sort(a+1,a+tot+1);
        cdq(1,tot);
        for(int i=1;i<=tot;i++)
        {
            if(a[i].op==2)
                ans[a[i].id]+=a[i].k*a[i].ans;
        }
        for(int i=1;i<=m;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}

B - Mokia

VJ链接：https://vjudge.net/contest/319165#problem/B

对于这种三维偏序，CDQ的神奇就显现出来啦，不用树套树，不怕炸空间（二维树状），CDQ+树状水过！

一维时间在初始化的时候排好序不用管了（不对时间分治省了sort），二维x用CDQ，三维y用树状。

对于（L，mid）操作按y坐标插入到树状数组中，对于（mid+1，R）的操作进行查询。

注意将树状数组中的操作还原以免对后续运算产生影响。

否则回溯之后（L，mid）中的值会被加多次，还原区间只包括（L，mid）（这里T了一发。。边界搞成R了我恨）

还原不要暴力mem或者fill，容易T掉。

还有很奇怪的一点是好像初值S对答案并无影响，最后的ans数组加不加S都能A。。。？？？（待解决

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=2e5+10;
#define pi  acos(-1.0)
#define INF  0x3f3f3f3f
#define mod   1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define lowbit(x)  ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int x,y,c,d,v,op;
int n,tot,cnt,maxn;
struct IN
{
    int x,y,op,id,c;
}a[MAXN],b[MAXN];
int  ans[MAXN],sum[MAXN*10];
void fix(int x,int v){for(;x<=maxn;x+=lowbit(x)) sum[x]+=v;}
int fund(int x){int re=0;for(;x;x-=lowbit(x)) re+=sum[x];return re;}

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;
    for(int i=l;i<=r;i++)
    {
        if(t1<=mid&&(t2>r||a[t1].x<=a[t2].x))
        {
            if(a[t1].op==1) fix(a[t1].y,a[t1].c);
            b[i]=a[t1++];
        }
        else
        {
            if(a[t2].op==2) ans[a[t2].id]+=a[t2].c*fund(a[t2].y);
            b[i]=a[t2++];
        }
    }
    for(int i=l;i<=mid;i++) if(a[i].op==1) fix(a[i].y,-a[i].c);
    for(int i=l;i<=r;++i) a[i]=b[i];//归并
}
int main()
{
    scanf("%*d%d",&maxn);
    tot=0;cnt=0;
    while(1)
    {
        s1(op);
        if(op==1)
        {
            s3(x,y,v);
            a[++tot]=(IN){x,y,1,0,v};
        }
        else if(op==2)
        {
            scanf("%d %d %d %d",&x,&y,&c,&d);
            x--;y--;cnt++;
            a[++tot]=(IN){c,d,2,cnt,1};
            a[++tot]=(IN){x,y,2,cnt,1};
            a[++tot]=(IN){x,d,2,cnt,-1};
            a[++tot]=(IN){c,y,2,cnt,-1};
        }
        else break;
    }
    cdq(1,tot);
    for(int i=1;i<=cnt;i++)
        printf("%d\n",ans[i]);
    return 0;
}

C - 陌上花开

VJ链接：https://vjudge.net/contest/319165#problem/C

很明显的三维偏序，，， x一维排序，y一维CDQ，z一维树状

值得注意的一点就是因为一开始可能有相等的需要去重，并记录有多少花和它相等，

判断去重后属于哪个级别就记录有多少元素对他满足三维偏序关系

ans[a[i].num+a[i].cnt]+=a[i].cnt一式中，ans[]中区分级别时，记得加上相等的数目cnt才是最后的级别，

对每个级别统计出现了多少花即可。

#include<cmath>
#include<cstdio>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=2e5+10;
#define pi  acos(-1.0)
#define INF  0x3f3f3f3f
#define mod   1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define lowbit(x)  ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n,tot,maxn;
struct IN
{
    int x,y,z,cnt,num;//num比他小的cnt和他相等的
    friend bool operator !=(const IN &a,const IN &b)
    {
        return a.x!=b.x||a.y!=b.y||a.z!=b.z;
    }
    friend bool operator <(const IN &a,const IN &b)
    {
        if(a.x!=b.x) return a.x<b.x;
        else if(a.y!=b.y) return a.y<b.y;
        return a.z<b.z;
    }
}v[MAXN],a[MAXN],b[MAXN];
int  ans[MAXN],sum[MAXN*10];
void fix(int x,int v){for(;x<=maxn;x+=lowbit(x)) sum[x]+=v;}
int fund(int x){int re=0;for(;x;x-=lowbit(x)) re+=sum[x];return re;}

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;
    for(int i=l;i<=r;i++)
    {
        if(t1<=mid&&(t2>r||a[t1].y<=a[t2].y))
            fix(a[t1].z,a[t1].cnt),b[i]=a[t1++];
        else
            b[i]=a[t2],b[i].num+=fund(a[t2++].z);
    }
    for(int i=l;i<=mid;i++) fix(a[i].z,-a[i].cnt);
    for(int i=l;i<=r;i++) a[i]=b[i];
}
int main()
{
    scanf("%d%d",&n,&maxn);
    for(int i=1;i<=n;i++)
        s3(v[i].x,v[i].y,v[i].z);
    sort(v+1,v+n+1);v[0].x=-1;tot=0;
    for(int i=1;i<=n;i++)
    {
        if(v[i]!=v[i-1]) a[++tot]=v[i];
        a[tot].cnt++;
    }
    cdq(1,tot);
    for(int i=1;i<=tot;i++)
        ans[a[i].num+a[i].cnt]+=a[i].cnt;
    for(int i=1;i<=n;i++)   printf("%d\n",ans[i]);
    return 0;
}

CDQ分治初识

概述

基本步骤

学到目前箬蒻的一些理解

理解不够题来凑

A - Tree 园丁的烦恼

B - Mokia

C - 陌上花开