本篇内容将持续更新。

CDQ 分治是一种离线的分治算法。其主要思想是，对于一个规模为 \(n\) 的问题，首先计算 \([1,\left \lfloor \dfrac n2 \right \rfloor],[\left \lfloor \dfrac n2 \right \rfloor+1,n]\) 这两个子问题内部的答案，再计算这两个子问题相互贡献的答案。

一个比较经典的问题是三维偏序问题：

给定 \(n\) 个三元组 \((a_1,b_1,c_1),(a_2,b_2,c_2),\cdots,(a_n,b_n,c_n)\)，求满足 \(a_i \leq a_j\) 且 \(b_i \leq b_j\) 且 \(c_i \leq c_j\) 的二元组 \(i,j\) 数量。没有两个三元组是完全相同的。

\(1 \leq n \leq 10^5, 1\leq a_i,b_i,c_i \leq 2 \times 10^5\)

首先可以按照 \(a\) 进行升序排序，消去一维影响。接下来，我们分治处理。对于当前处理的区间 \([l,r]\)，如果 \(l=r\)，那什么都不用做。否则，递归处理 \([l,mid]\) 和 \([mid+1,r]\) 内部的贡献，并将它们分别按照 \(b\) 升序排序。这样，区间 \([l,mid]\) 和 \([mid+1,r]\) 满足：

• 区间内部三元组的 \(b\) 递增。
• 区间 \([l,mid]\) 内部任意三元组的 \(a\) 都小于等于区间 \([mid+1,r]\) 内部任意三元组的 \(a\)。这是因为在操作前按照 \(a\) 对所有三元组进行了排序，就算区间内部按照 \(b\) 进行了重排也不影响该性质。

我们维护一个树状数组。我们顺序处理区间 \([mid+1,r]\) 的每一个三元组。设当前处理到的三元组编号为 \(j(mid < j< r)\)，将编号为 \(k (l \le k\leq mid)\) 的所有满足 \(b_k \leq b_j\) 的三元组的 \(c_k\) 加入树状数组中，然后在树状数组中查询小于等于 \(c_j\) 的值数量，就得到了 \([l,mid]\) 对 \(j\) 的贡献。

这样看上去复杂度根本不对？对于一个长度为 \(2m\) 的区间，复杂度似乎是 \(O(m^2 + m \log \max\{c\})\) 的...

因为两个区间内部的 \(b\) 递增，所以在处理的过程中，树状数组中的 \(c_k\) 一定是从 \(c_l\) 开始，连续的一段。用一个左指针维护当前加入的 \(c_k\) 的最后一个位置 \(pos\)。当我们从处理 \(j-1\) 变为处理 \(j\) 时，就把 \(pos\) 一直往右移动，直到 \(b_{pos} > b_j\) 或者 \(pos > mid\)。

对于一个长度为 \(2m\) 的区间，\(pos\) 至多移动 \(m\) 次，复杂度瓶颈变为树状数组的 \(O(m \log \max\{c\})\)。

递归一次区间长度减半，那么至多递归 \(O(\log n)\) 次，总复杂度为 \(O(n \log n \log \max\{c\})\)。

例题 [BOI2007]Mokia

题意

给定 \(w \times w\) 的矩阵，初始全 \(0\)，要求支持单点修改，子矩阵求和。

\(1 \leq w \leq 2 \times 10^6\)，修改次数 $ \leq 1.6 \times 10^5$，查询次数 $ \leq 10^4$

题解

首先将询问差分一下，对于子矩阵 \((lx,ly,rx,ry)\) 的查询可以转化为 \((1,1,rx,ry)-(1,1,lx-1,ry)-(1,1,rx,ly-1)+(1,1,lx-1,ly-1)\)。

而对于 \((1,1,x,y)\) 的查询，其实就是查有多少个在 \((a,b)\) 的修改满足 \(a \leq x,b \leq y\) 且该修改在查询之前。

将时间作为 \(a\)，\(x\) 坐标作为 \(b\)，\(y\) 坐标作为 \(c\)，就是一个三维偏序问题。

# include <bits/stdc++.h>

const int N=100010,MAXW=2e6+10,INF=0x3f3f3f3f;

struct Node{
	int ti,x,y;
	int id,val;
}a[N*8];

int w,cnt;
int ans[N];
int querytot;
int sum[MAXW];
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}

inline bool cmp_x(const Node u,const Node &v){
	return (u.x==v.x)?(u.y<v.y):(u.x<v.x);
}
inline int lowbit(int x){
	return x&(-x);
}
inline void add(int x,int v){
	if(!x)
		return;
	for(;x<=w;x+=lowbit(x)){
		sum[x]+=v;
	}
	return;
}
inline int query(int x){
	int res=0;
	for(;x;x-=lowbit(x)){
		res+=sum[x];
	}
	return res;
}
void CDQ(int l,int r){
	if(l==r){
		return;
	}
	int mid=(l+r)>>1,pL=l,pR=mid+1;
	CDQ(l,mid),CDQ(mid+1,r);
	std::sort(a+l,a+1+mid,cmp_x),std::sort(a+mid+1,a+r+1,cmp_x); // 因为复杂度瓶颈是树状数组的 log 这里直接 sort 也是没有问题的（当然也可以归并排序）
	for(;pR<=r;++pR){
		for(;pL<=mid&&a[pL].x<=a[pR].x;++pL){
			if(!a[pL].id){ // 是修改操作
				add(a[pL].y,a[pL].val);
			}
		}
		if(a[pR].id){ // 是查询操作
			ans[a[pR].id]+=a[pR].val*query(a[pR].y);
		}
	}
	for(int i=l;i<pL;++i){
		if(!a[i].id) // 还原树状数组
			add(a[i].y,-a[i].val);
	}
	return;
}
int main(void){
	read(),w=read();
	for(int opt,i=1;(opt=read())!=3;++i){
		if(opt==1){
			int x=read(),y=read(),v=read();
			a[++cnt]=(Node){i,x,y,0,v}; // 如果是修改操作 val 就是要加上的值
		}else{
			++querytot;
			int lx=read(),ly=read(),rx=read(),ry=read();
			a[++cnt]=(Node){i,rx,ry,querytot,1};
			a[++cnt]=(Node){i,rx,ly-1,querytot,-1};
			a[++cnt]=(Node){i,lx-1,ry,querytot,-1};
			a[++cnt]=(Node){i,lx-1,ly-1,querytot,1}; // 如果是查询操作 id 就是询问编号 val 是该前缀矩阵的权值
		}
	}
	CDQ(1,cnt);
	for(int i=1;i<=querytot;++i){
		printf("%d\n",ans[i]);
	}
	return 0;
}