tip：
CDQ 分治主要处理三维偏序问题，解题时主要是找出比较量（三个或两个），并找出适当排序顺序（有时不需））。
CDQ 分治常常与树状数组搭配，树状数组主要用来统计前缀和（权值前缀和 / 排名）、最值、逆序对。
实战：
T1：陌上花开
题干：
有 n 朵花,每朵花有三个属性:花形 (s)、颜色 (c)、气味 (m),用三个整数表示。现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花 A 比另一朵花 B 要美丽,当且仅当 Sa>=Sb , Ca>=Cb , Ma>=Mb 。
显然,两朵花可能有同样的属性。需要统计出每个等级的花的数量。
题解：
比较明显就可以看出这是一道 CDQ 分治，三个比较量就是 S、C、M，排序顺序对这道题来说没有影响。
需要注意的是，我们可以发现有可能两朵花的属性完全一样，根据题意来看，这两朵花互相更美丽。。。
注意一下我们需要求出的是每个等级的花的数量，而不是每朵花的等级。
在统计答案时需要去重，将完全一样的花合成一朵，只是权值增加了；
当然，也可以不去重，只是我们需要找出 完全相同的花中答案最大的 作为这种花的等级。
我们可以将 S sort 一下，将 C 用 CDQ 分治解决，将 M 压进树状数组中来统计。
在统计答案时（通法），我们直接在结构体中建立一个 ans 变量。因为本题的结果与 ans 更新的顺序没有直接关系，能更新就更新即可。
Code：
1 #include<cstdio>
2 #include<cstring>
3 #include<cstdlib>
4 #include<algorithm>
5 #define $ 200010
6 using namespace std;
7 int m,n,k,t,ans[$*2],cnt,tr[$*2];
8 struct tree{
9 int s,c,m,t,sum,ans;
10 friend bool operator != (tree x,tree y){
11 if(x.s!=y.s) return 1;
12 if(x.c!=y.c) return 1;
13 if(x.m!=y.m) return 1;
14 return 0;
15 }
16 friend bool operator < (tree x,tree y){
17 if(x.s!=y.s) return x.s<y.s;
18 if(x.c!=y.c) return x.c<y.c;
19 return x.m<y.m;
20 }
21 }a[$],pre[$],now[$];
22 inline void add(int x,int add){
23 if(x==0) return;
24 for(register int i=x;i<=k;i+=i&(-i)) tr[i]+=add;
25 }
26 inline int ask(int x,int ans=0){
27 for(register int i=x;i>=1;i-=i&(-i)) ans+=tr[i];
28 return ans;
29 }
30 inline void CDQ(int l,int r){
31 if(l==r) return;
32 int mid=(l+r)>>1;
33 CDQ(l,mid); CDQ(mid+1,r);
34 int left=l,right=mid+1,tip=0;
35 while(left<=mid&&right<=r){
36 if(a[left].c<=a[right].c)
37 add(a[left].m,a[left].sum), now[++tip]=a[left++];
38 else
39 a[right].ans+=ask(a[right].m), now[++tip]=a[right++];
40 }
41 while(right<=r)
42 a[right].ans+=ask(a[right].m), now[++tip]=a[right++];
43 for(register int i=l;i<left;++i) add(a[i].m,0);
44 while(left<=mid) now[++tip]=a[left++];
45 for(register int i=l;i<=r;++i) a[i]=now[i-l+1];
46 }
47 signed main(){
48 scanf("%d%d",&n,&k);
49 for(register int i=1;i<=n;++i)
50 scanf("%d%d%d",&pre[i].s,&pre[i].c,&pre[i].m);
51 sort(pre+1,pre+n+1);
52 for(register int i=1,sum=1;i<=n;++i,++sum)
53 if(pre[i+1]!=pre[i]) a[++cnt]=pre[i], a[cnt].sum=sum, sum=0;
54 CDQ(1,cnt);
55 for(register int i=1;i<=cnt;++i) ans[a[i].ans+a[i].sum]+=a[i].sum;
56 for(register int i=1;i<=n;++i) printf("%d
",ans[i]);
57 }
1 #include<cstdio>
2 #include<cstring>
3 #include<cstdlib>
4 #include<algorithm>
5 #define $ 200010
6 using namespace std;
7 int m,n,k,t,ans[$*2],cnt,tr[$*2];
8 struct tree{
9 int s,c,m,t,ans;
10 friend bool operator == (tree x,tree y){
11 if(x.s!=y.s) return 0;
12 if(x.c!=y.c) return 0;
13 if(x.m!=y.m) return 0;
14 return 1;
15 }
16 friend bool operator < (tree x,tree y){
17 if(x.s!=y.s) return x.s<y.s;
18 if(x.c!=y.c) return x.c<y.c;
19 if(x.m!=y.m) return x.m<y.m;
20 return x.ans<y.ans;
21 }
22 }a[$],pre[$],now[$];
23 inline void add(int x,int add){
24 if(x==0) return;
25 for(register int i=x;i<=k;i+=i&(-i)) tr[i]+=add;
26 }
27 inline int ask(int x,int ans=0){
28 for(register int i=x;i>=1;i-=i&(-i)) ans+=tr[i];
29 return ans;
30 }
31 inline void CDQ(int l,int r){
32 if(l==r) return;
33 int mid=(l+r)>>1;
34 CDQ(l,mid); CDQ(mid+1,r);
35 int left=l,right=mid+1,tip=0;
36 while(left<=mid&&right<=r){
37 if(a[left].c<=a[right].c)
38 add(a[left].m,1), now[++tip]=a[left++];
39 else
40 a[right].ans+=ask(a[right].m), now[++tip]=a[right++];
41 }
42 while(right<=r)
43 a[right].ans+=ask(a[right].m), now[++tip]=a[right++];
44 for(register int i=l;i<left;++i) add(a[i].m,0);
45 while(left<=mid) now[++tip]=a[left++];
46 for(register int i=l;i<=r;++i) a[i]=now[i-l+1];
47 }
48 signed main(){
49 scanf("%d%d",&n,&k);
50 for(register int i=1;i<=n;++i)
51 scanf("%d%d%d",&a[i].s,&a[i].c,&a[i].m);
52 sort(a+1,a+n+1); CDQ(1,cnt); sort(a+1,a+n+1);
53 int tip=a[cnt].ans;
54 for(register int i=cnt;i>=1;--i){
55 if(a[i]==a[i-1]) ans[tip]++;
56 else tip=
57 }
58 for(register int i=1;i<=n;++i) printf("%d
",ans[i]);
59 }
T2：Mokia / 简单题
题干：
维护一个 W * W 的矩阵，初始值均为 S .每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数 M<=160000,询问数 Q<=10000 , W<=2000000.
第一行两个整数 , S , W ;其中 S 为矩阵初始值; W 为矩阵大小
接下来每行为一下三种输入之一(不包含引号):
"1 x y a"
"2 x1 y1 x2 y2"
"3"
输入 1 :你需要把 (x,y) (第 x 行第 y 列)的格子权值增加 a
输入 2 :你需要求出以左下角为 (x1,y1) ,右上角为 (x2,y2) 的矩阵内所有格子的权值和,并输出
输入 3 :表示输入结束
题解：
看到 w=2000000 ，数组模拟不优秀，空间、时间复杂度都不行。
我们可以发现，每种操作都与时间有关，结果的更新也与时间有关；同时操作又与坐标有关。发现这几个变量，我们就可以想到用 CDQ 分治。
但是‘2’操作有 4 个坐标，用哪两个呢？其实我们不难看出只有最外面的那个坐标起决定作用，因为修改操作只有在访问区域内才可能做贡献。
我们可以利用单步容斥的方法，将一个查询操作分成 4 个查询操作，时间戳一样，还是按照原来的排序顺序（t > x > y）排序即可。
我们发现， $ans$ 的结果与更新它的时间没有关系，我们完全可以将其作为一个二维偏序问题来解决。
Code：
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #define $ 800010 6 using namespace std; 7 int m,n,k,t,s,w,cnt,ans[$],tr[$*3],x,y,xx,yy,derta,opt,num; 8 struct tree{ 9 int opt,x,y,val,t; 10 friend bool operator < (tree x,tree y){ 11 if(x.x!=y.x) return x.x<y.x; 12 if(x.y!=y.y) return x.y<y.y; 13 return x.opt<y.opt; 14 } 15 }a[$],now[$]; 16 inline void add(int x,int add){ 17 if(x==0) return; 18 if(add==0){ 19 for(register int i=x;i<=w;i+=i&(-i)) tr[i]=0; 20 return; 21 } 22 for(register int i=x;i<=w;i+=i&(-i)) tr[i]+=add; 23 } 24 inline int ask(int x,int ans=0){ 25 for(register int i=x;i>=1;i-=i&(-i)) ans+=tr[i]; 26 return ans; 27 } 28 inline void CDQ(int l,int r){ 29 if(l==r) return ; 30 int mid=(l+r)>>1,tip=0,left=l,right=mid+1; 31 CDQ(l,mid); CDQ(mid+1,r); 32 while(left<=mid&&right<=r){ 33 if(a[left].x<=a[right].x){ 34 if(a[left].opt==0) add(a[left].y,a[left].val); 35 now[++tip]=a[left]; ++left; 36 } 37 else{ 38 if(a[right].opt==1) 39 ans[a[right].t]+=ask(a[right].y)*a[right].val; 40 now[++tip]=a[right]; ++right; 41 } 42 } 43 while(left<=mid) now[++tip]=a[left], ++left; 44 while(right<=r){ 45 if(a[right].opt) ans[a[right].t]+=ask(a[right].y)*a[right].val; 46 now[++tip]=a[right]; ++right; 47 } 48 for(register int i=l;i<=mid;++i) add(a[i].y,0); 49 for(register int i=l;i<=r;++i) a[i]=now[i-l+1]; 50 } 51 signed main(){ 52 scanf("%d%d",&s,&w); 53 while(~scanf("%d",&opt)){ 54 if(opt==1){ 55 scanf("%d%d%d",&x,&y,&derta); 56 a[++cnt]=(tree){ 0,x,y,derta,0 }; 57 } 58 if(opt==2){ 59 scanf("%d%d%d%d",&x,&y,&xx,&yy); ++num; 60 ans[num]=(yy-y+1)*(xx-x+1)*s; 61 a[++cnt]=(tree){ 1,xx,yy,1,num }; 62 a[++cnt]=(tree){ 1,x-1,y-1,1,num }; 63 a[++cnt]=(tree){ 1,x-1,yy,-1,num }; 64 a[++cnt]=(tree){ 1,xx,y-1,-1,num }; 65 } 66 if(opt==3) break; 67 } 68 CDQ(1,cnt); 69 for(register int i=1;i<=num;++i) printf("%d ",ans[i]); 70 }
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdlib> 5 #define $ 2200000 6 #define int long long 7 using namespace std; 8 struct tree { int t,x,y,opt,f,val; }a[$],now[$]; 9 int s,w,tot,opt,up,tr[$*8]; 10 inline bool cmp(const tree &a,const tree &b){ 11 if(a.t!=b.t) return a.t<b.t; 12 if(a.x!=b.x) return a.x<b.x; 13 return a.y<b.y; 14 } 15 inline void add(int x,int add){ 16 if(add==0){ 17 for(register int i=x;i<=w;i+=i&(-i)) tr[i]=0; 18 return; 19 } 20 for(register int i=x;i<=w;i+=i&(-i)) tr[i]+=add; 21 } 22 inline int query(int x,int ans=0){ 23 for(register int i=x;i>=1;i-=i&(-i)) ans+=tr[i]; 24 return ans; 25 } 26 inline void CDQ(int l,int r){ 27 if(l==r)return; 28 int mid=(l+r)>>1,left=l,right=mid+1,tip=-1; 29 CDQ(l,mid),CDQ(mid+1,r); 30 while(left<=mid&&right<=r){ 31 if(a[left].x<=a[right].x){ 32 if(!a[left].opt) add(a[left].y,a[left].val); 33 now[++tip]=a[left++]; 34 }else{ 35 if(a[right].opt) a[right].f+=query(a[right].y); 36 now[++tip]=a[right++]; 37 } 38 } 39 while(right<=r){ 40 if(a[right].opt) a[right].f+=query(a[right].y); 41 now[++tip]=a[right++]; 42 } 43 for(register int i=l;i<left;++i) add(a[i].y,0); 44 while(left<=mid) now[++tip]=a[left++]; 45 for(register int i=l;i<=r;++i) a[i]=now[i-l]; 46 } 47 signed main(){ 48 scanf("%lld%lld",&s,&w); ++w; 49 for(register int i=1,x,y,z,xx,yy;;++i){ 50 scanf("%lld",&opt); 51 if(opt==1){ 52 scanf("%lld%lld%lld",&x,&y,&z); 53 a[++tot]=(tree){i,x+1,y+1,0,0,z}; 54 } 55 if(opt==2){ 56 scanf("%lld%lld%lld%lld",&x,&y,&xx,&yy); 57 a[++tot]=(tree){ i,xx+1,yy+1,1,0,0 }; 58 a[++tot]=(tree){ i,x,yy+1,-1,0,0 }; 59 a[++tot]=(tree){ i,xx+1,y,-1,0,0 }; 60 a[++tot]=(tree){ i,x,y,1,0,0 }; 61 } 62 if(opt==3) break; 63 } 64 sort(a+1,a+1+tot,cmp); CDQ(1,tot); 65 sort(a+1,a+1+tot,cmp); 66 for(register int i=1;i<=tot;i+=4){ 67 if(!a[i].opt) continue; 68 int ans=0; 69 for(register int j=1;j<=4;++j) 70 ans+=a[i+j-1].opt*(a[i+j-1].f+a[i+j-1].x*a[i+j-1].y*s); 71 printf("%lld ",ans); 72 } 73 }
T3：天使玩偶
题干：
题解：
注意曼哈顿距离是有绝对值的，我们不可以简单地将 $x+y$ 压入树状数组来比较，只有这个点在目标节点的左下方才可以进行比较。
我们就可以进行 4 次 CDQ，每次都变换一下每个点的坐标，就相当于是转动了坐标系，分 4 次将答案更新完成。
我们又可以发现，更新答案与时间无相互限制，可以不保证 t 的单调。
Code：
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #define $ 1001000 6 #define inf 0x3f3f3f3 7 #define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++) 8 using namespace std; 9 int m,n,k,t,cnt,num,ans[$],tr[$*2],maxx; 10 struct tree{ int opt,x,y; }a[$],now[$],pre[$]; 11 char xB[(1<<15)+10],*xS=xB,*xT=xB; 12 inline int read(int sum=0){ 13 register char ch=getchar(); 14 for(sum=0;ch<'0'||ch>'9';ch=getchar()); 15 for(;ch>='0'&&ch<='9';sum=(sum<<1)+(sum<<3)+ch-'0',ch=getchar()); 16 return sum; 17 } 18 inline int min(int x,int y){ return x<y?x:y; } 19 inline int max(int x,int y){ return x>y?x:y; } 20 inline void add(int x,int add){ 21 if(x==0) return; 22 if(add==-inf){ 23 for(register int i=x;i<=maxx;i+=i&(-i)) tr[i]=0; 24 return; 25 } 26 for(register int i=x;i<=maxx;i+=i&(-i)) tr[i]=max(tr[i],add); 27 } 28 inline int ask(int x,int ans=0){ 29 for(register int i=x;i>=1;i-=i&(-i)) ans=max(ans,tr[i]); 30 return (ans==0)?-inf:ans; 31 } 32 inline void CDQ(int l,int r){ 33 if(l==r) return; 34 int mid=(l+r)>>1,left=l,right=mid+1,tip=0; 35 CDQ(l,mid); CDQ(mid+1,r); 36 while(left<=mid&&right<=r){ 37 if(a[left].x<=a[right].x){ 38 if(!a[left].opt) add(a[left].y,a[left].x+a[left].y); 39 now[++tip]=a[left]; ++left; 40 } 41 else{ 42 if(a[right].opt) 43 ans[a[right].opt]=min(ans[a[right].opt],a[right].x+a[right].y-ask(a[right].y)); 44 now[++tip]=a[right]; ++right; 45 } 46 } 47 while(right<=r){ 48 if(a[right].opt) 49 ans[a[right].opt]=min(ans[a[right].opt],a[right].x+a[right].y-ask(a[right].y)); 50 now[++tip]=a[right], ++right; 51 } 52 for(register int i=l;i<left;++i) add(a[i].y,-inf); 53 while(left<=mid) now[++tip]=a[left], ++left; 54 for(register int i=l;i<=r;++i) a[i]=now[i-l+1]; 55 } 56 signed main(){ 57 memset(ans,63,sizeof(ans)); 58 scanf("%d%d",&n,&m); 59 for(register int i=1,x,y;i<=n;++i){ 60 x=read(), y=read(); 61 pre[++cnt]=(tree){ 0,x+1,y+1 }; 62 maxx=max(maxx,x+y); 63 } 64 for(register int i=1,x,y,opt;i<=m;++i){ 65 opt=read(), x=read(), y=read(); 66 if(opt==2) opt=++num; 67 else opt=0; 68 pre[++cnt]=(tree){ opt,x+1,y+1 }; 69 maxx=max(maxx,x+y); 70 } 71 maxx+=100; 72 for(register int i=1;i<=cnt;++i) a[i]=(tree){ pre[i].opt,pre[i].x,pre[i].y }; 73 CDQ(1,cnt); 74 for(register int i=1;i<=cnt;++i) a[i]=(tree){ pre[i].opt,maxx-pre[i].x,pre[i].y }; 75 CDQ(1,cnt); 76 for(register int i=1;i<=cnt;++i) a[i]=(tree){ pre[i].opt,pre[i].x,maxx-pre[i].y }; 77 CDQ(1,cnt); 78 for(register int i=1;i<=cnt;++i) a[i]=(tree){ pre[i].opt,maxx-pre[i].x,maxx-pre[i].y }; 79 CDQ(1,cnt); 80 for(register int i=1;i<=num;++i) printf("%d ",ans[i]); 81 }
T4：动态逆序对
题干：
对于序列 A ，它的逆序对数定义为满足 i A j 的数对 (i,j) 的个数。给 1 到 n 的一个排列，按照某种顺序依次删除 m 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
题解：
‘按照顺序删除一个数’可以转化为‘按照顺序添加一个数’；相应地，‘删除元素之前统计’就是‘添加元素之后统计’，这就符合我们平时做题时的按序添加的 CDQ 分治问题。
发现时间与答案统计有关，我们就还是三维排序即可。
Code：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define $ 600100 5 #define int long long 6 using namespace std; 7 int m,n,k,t,cnt,mrk[$],ans[$/2],maxx,tr[$*10]; 8 struct tree{ 9 int t,id,w,ans; 10 friend bool operator < (tree x,tree y){ 11 if(x.t!=y.t) return x.t<y.t; 12 if(x.id!=y.id) return x.id<y.id; 13 return x.w<y.w; 14 } 15 }a[$],now[$],pre[$]; 16 inline int max(int x,int y){ return x>y?x:y; } 17 inline void add(int x,int add){ 18 if(x==0) return ; 19 for(register int i=x;i<=maxx;i+=i&(-i)) tr[i]+=add; 20 } 21 inline int ask(int x,int ans=0){ 22 for(register int i=x;i>=1;i-=i&(-i)) ans+=tr[i]; 23 return ans; 24 } 25 inline void CDQ(int l,int r){ 26 if(l==r) return; 27 int mid=(l+r)>>1,left=l,right=mid+1,tip=-1; 28 CDQ(l,mid); CDQ(mid+1,r); 29 while(left<=mid&&right<=r){ 30 if(a[left].id<a[right].id) 31 add(a[left].w,1), now[++tip]=a[left++]; 32 else 33 ans[a[right].t]+=ask(a[right].w), now[++tip]=a[right++]; 34 } 35 while(right<=r) 36 ans[a[right].t]+=ask(a[right].w), now[++tip]=a[right++]; 37 for(register int i=l;i<left;++i) add(a[i].w,-1); 38 while(left<=mid) now[++tip]=a[left++]; 39 for(register int i=l;i<=r;++i) a[i]=now[i-l]; 40 } 41 signed main(){ 42 scanf("%lld%lld",&n,&m); cnt=m; 43 for(register int i=1;i<=n;++i) 44 scanf("%lld",&a[i].w), a[i].id=i, maxx=max(maxx,a[i].w); 45 for(register int i=1,x;i<=m;++i) scanf("%lld",&x), mrk[x]=i; 46 for(register int i=1;i<=n;++i) if(mrk[i]==0) mrk[i]=++cnt; 47 for(register int i=1;i<=n;++i) a[i].t=n-mrk[a[i].w]+1; 48 for(register int i=1;i<=n;++i) a[i].w=maxx-a[i].w+1; 49 sort(a+1,a+n+1); CDQ(1,n); 50 for(register int i=1;i<=n;++i) a[i].w=maxx-a[i].w+1, a[i].id=n-a[i].id+1; 51 sort(a+1,a+n+1); CDQ(1,n); 52 for(register int i=1;i<=n;++i) ans[i]+=ans[i-1]; 53 for(register int i=n;i>=n-m+1;--i) printf("%lld ",ans[i]); 54 }