CDQ 分治

CDQ 分治，是一种将操作序列离线下来后，按照时间分治求解的算法。

具体的实现是这样的：

定义 $\operatorname{solve}(l, r)$ 计算对于每一个在 $[l, r]$ 中的操作 $k$ 里，$[l, k - 1]$ 中的修改操作的影响。

$\operatorname{solve}(l, r)$ 的实现具体是这样的：

1. 设 $mid = \left\lfloor\dfrac{l + r}{2}\right\rfloor$。
2. 递归运算 $\operatorname{solve}(l, mid)$ 与 $\operatorname{solve}(mid + 1, r)$。
3. 计算 $[l, mid]$ 中的修改操作对 $[mid + 1, r]$ 里的查询操作带来的影响。

显然，$\operatorname{solve}(l, r)$ 的递归边界为 $l = r$。

正确性证明

设在 $[l, r]$ 中的 $k$ 为查询操作。

1. 如果 $k \le mid$，它被 $\operatorname{solve}(l, mid)$ 计算过了；
2. 如果 $k > mid$，在 $[l, mid]$ 中的修改操作在操作三中计算过了，在 $[mid + 1, k]$ 中的修改操作被 $\operatorname{solve}(mid + 1, r)$ 计算过了。

【模板】三维偏序（陌上花开）

首先，我们可以按照 $a_i$ 排序。

然后，我们就可以将问题转换，修改操作就相当于在序列里插入一个 $(b_i, c_i)$。

步骤三就相当于计算两个点分别在不同区间里的对个数。

因为已经对序列按照 $a_i$ 排序，所以左半区间的 $a_i$ 都小于右半区间的 $a_i$，所以可以直接对两个区间按照 $b_i$ 排序。

排序后，右半区间对应满足 $b_i$ 要求的左半区间的点个数单独上升，直接用两个指针扫过去即可。

满足 $c_i$ 要求的点个数用树状数组维护。

#include <algorithm>
#include <cstring>
#include <cstdio>
inline int lowbit(int x){return x & -x;}
struct node{
	int a, b, c, t, ans;
	inline bool operator==(node x)const{
		return a == x.a && b == x.b && c == x.c;
	}
}_[100001], a[100001];
inline bool cmpc(node a, node b){
	return a.c < b.c;
}
inline bool cmpb(node a, node b){
	if (a.b == b.b) return cmpc(a, b);
	return a.b < b.b;
}
inline bool cmpa(node a, node b){
	if (a.a == b.a) return cmpb(a, b);
	return a.a < b.a;
}
int tr[200001];
void update(int p, int x){
	while (p <= 200000) tr[p] += x, p += lowbit(p);
}
int query(int p){
	int ans = 0;
	while (p) ans += tr[p], p -= lowbit(p);
	return ans;
}

using namespace std;

int l, n, k, cnt[100001];
void solve(int l, int r){
	if (l == r) return;
	int mid = l + r >> 1;
	solve(l, mid), solve(mid + 1, r);
	sort(a + l, a + mid + 1, cmpb), sort(a + mid + 1, a + r + 1, cmpb);
	int j = l;
	for (int i = mid + 1;i <= r;i ++){
		while (a[j].b <= a[i].b && j <= mid) update(a[j].c, a[j].t), j ++;
		a[i].ans += query(a[i].c);
	}
	for (int i = l;i < j;i ++) update(a[i].c, -a[i].t);
}
int main(){
	scanf("%d%d", &l, &k);
	for (int i = 1;i <= l;i ++) scanf("%d%d%d", &_[i].a, &_[i].b, &_[i].c);
	sort(_ + 1, _ + l + 1, cmpa);
	for (int i = 1;i <= l;i ++){
		if (_[i].a != _[i - 1].a || _[i].b != _[i - 1].b || _[i].c != _[i - 1].c) a[++ n] = _[i], a[n].t = 1;
		else a[n].t ++;
	}
	solve(1, n);
	for (int i = 1;i <= n;i ++) cnt[a[i].ans + a[i].t - 1] += a[i].t;
	for (int i = 0;i < l;i ++) printf("%d\n", cnt[i]);
}

例题

[CQOI2011] 动态逆序对

[Violet] 天使玩偶 / SJY摆棋子

[BOI2007] Mokia 摩基亚