CDQ分治

CDQ分治大致有 3 种用法

解决和点对有关的问题

1. 找到序列的重点 $mid$
2. 将所有点对 $(i,j)$ 分成 3 类 a. $1 \le i \le mid,1 \le j \le mid$ b. $1\le i \le mid,mid+1 \le j \le n$ c. $mid+1 \le i \le n,mid+1 \le j \le n$
3. 第一类和第三类点对递归处理
4. 设法处理第二类点对

例题：三维偏序

代码实现

#include<bits/stdc++.h>
using namespace std;
int N,ans[1000005],K,c[200005],m;
struct AS{
    int a,b,c,cnt,ans;
}a[100005],b[100005];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
bool cmp1(AS A,AS B){return (A.a<B.a)||(A.a==B.a&&A.b<B.b)||(A.a==B.a&&A.b==B.b&&A.c<B.c);}
bool cmp2(AS A,AS B){return (A.b<B.b)||(A.b==B.b&&A.c<B.c);}
void add_x(int x,int data){
    for(int i=x;i<=K;i+=i&-i)c[i]+=data;
    return ;
}
int get(int x){
    int S=0;
    for(int i=x;i;i-=i&-i)S+=c[i];
    return S;
}
void CDQ(int l,int r){
    if(l==r)return ;
    int mid=(r-l>>1)+l;
    CDQ(l,mid);CDQ(mid+1,r);
    sort(b+l,b+mid+1,cmp2);
    sort(b+mid+1,b+r+1,cmp2);
    int i,j=l;
    for(i=mid+1;i<=r;i++){
        while(b[i].b>=b[j].b&&j<=mid){
            add_x(b[j].c,b[j].cnt);
            j++;
        }
        b[i].ans+=get(b[i].c);
    }
    for(int i=l;i<j;i++)add_x(b[i].c,-b[i].cnt);
}
int main(){
    N=read();K=read();
    for(int i=1;i<=N;i++)a[i].a=read(),a[i].b=read(),a[i].c=read();
    sort(a+1,a+1+N,cmp1);
    for(int i=1;i<=N;i++){
        if(a[i].a==a[i-1].a&&a[i].b==a[i-1].b&&a[i].c==a[i-1].c){b[m].cnt++;continue;}
        m++;b[m].a=a[i].a;b[m].b=a[i].b;b[m].c=a[i].c;b[m].cnt++;
    }
    CDQ(1,m);
    for(int i=1;i<=m;i++)ans[b[i].ans+b[i].cnt-1]+=b[i].cnt;
    for(int i=0;i<N;i++)printf("%d\n",ans[i]);
    return 0;
}

CDQ 分治优化 1D/1D 动态规划的转移

处理这一类问题时，需要先处理 solve(l,mid)，然后处理 $l\le j \le mid,mid+1 \le j \le r$ 的点对，最后处理 solve(mid+1,r)

而三位偏序中，不需要考虑这个问题

原因是 DP 的转移必须是有序的

将动态问题转化为静态问题

前两种方法中，CDQ分治的目的是将序列之后递归处理点对之间的关系。这一类做法是将时间序列进行拆分

我们先递归处理 $(l,mid)(mid+1,r)$ 之间的修改-询问关系，然后处理 $l\le i \le mid,mid+1 \le j \le r$ 的修改-询问关系

• 注意，如果修改是非独立的话，例如赋值操作，那么第二类就要放在一三类之中，和 1D 动态规划的优化一样