分治（二）

Posted on | In | | Visitors:
Words count in article: 2.1k | Reading time ≈ 9

48a96d88a399214ebc9c7704065fb38f.jpg

CDQ分治和整体二分都属于离线算法

CDQ分治

CDQ分治的流程与普通分治的流程区别在于，当我们递归解决[L,M]和[M+1,R]区间后，除了将两个子区间的答案合并还要再加上右区间对左区间的贡献。
CDQ分治主要用于求解偏序问题。

下面用一个简单的示例说明CDQ的基本思想。

CDQ分治求逆序数

求逆序数实质是一个二维偏序问题，相当于一个由有序点对$(x,y)$组成的集合，求对于每个$(x_i,y_i)$有多少对$(x_j,y_j)$使得$x_i>x_j且y_i<y_j$的和。
首先一个区间其下标必然是有序的，于是我们只用考虑用$y$如何进行统计。那么参照上面所说的CDQ分治的思想，我们分别计算左右区间的逆序对个数并求和，然后算出右区间对左区间的贡献，总和即为整个当前区间的逆序对数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ll CDQ(int *p, int len) {
    //p开始的len个元素为当前区间，区间长度为len
    if (len == 1)return 0;//只有一个数显然逆序数为0
    int mid = len >> 1;
    ll ans = CDQ(p, mid) + CDQ (p + mid, len - mid);//分治，左右区间分别求解
    //此处应该将整个区间排序用双指针算出右区间对左区间的贡献，考虑到我们分治的过程
    //我们可以直接在分治过程中通过归并排序来减少复杂度
    int i = 0, j = mid, k = 0;
    while (i < mid && j < len) {
        if (p[i] <= p[j])tmp[k++] = p[i++];//不构成逆序对
        else {
            ans += mid - i;//p[i]后面的数都比p[i]大，因此也比p[j]大，将这部分计入右区间对左区间的贡献
            tmp[k++] = p[j++];
        }
    }
    while (i < mid)tmp[k++] = p[i++];
    while (j < len)tmp[k++] = p[j++];
    for (int i = 0; i < k; ++i)p[i] = tmp[i];//tmp存储的是归并后有序的区间，用其更新p
    return ans;
}

其他问题

值得一提的是，通常在进行CDQ分治之前我们会将数组排序，来确保可以通过计算右区间中每个点对左区间的贡献来得到正确答案。
对于多维偏序问题，我们依然可以使用CDQ分治，例如三维偏序，我们可以对第一维排序、第二维CDQ、第三维用数据结构或CDQ统计答案。
来看一个三维偏序的问题。
洛谷P3810 【模板】三维偏序（陌上花开）
我们很容易就想到，先以a为第一关键字、b为第二关键字、c为第三关键字排序，每次将区间分成两半，这样左区间的a都是小于等于右区间的a的，这样我们只需要计算对右边每对(b,c)左边有多少对满足条件的(b,c)即可
显然，b如果在两个区间内分别有序，我们的计算将会非常方便，用双指针扫一遍，若右区间的b大于等于左区间的b，则此时左区间的c就有可能对右区间的c产生贡献，因此我们用一个c值域上的树状数组维护当前有多少产生贡献的c，在右区间的b小于左区间的b时查询此时的贡献。
但是这里存在一个问题，此处我们用CDQ分治，要求只能是左区间对右区间产生贡献，但如果有a b c相同的元素分别属于左右区间，这时候右区间对左区间也能产生贡献。而我们的解决方法就是在开始的时候就对整个数组进行去重操作，记录下每个元素的个数有多少，然后对不同元素间进行上述分治+树状数组求解，每个元素的答案再加上相同元素个数-1（其他所有元素都对他产生贡献）就是该元素真正的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define jh(x, y) x ^= y ^= x ^= y
#define lowbit(x) (x & -x)
const double pi = 3.141593;
typedef long long ll;
const int N = 2e5 + 5, INF = 0x3f3f3f3f, mod = 1e9 + 7;
using namespace std;
namespace fast_IO {
	ll read() {
		char c;
		ll x = 0;
		bool flag = false;
		while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
		if (c == EOF)return c; if (c == '-')flag = true; else x = c ^ 48;
		while ((c = getchar()) != ' ' && c != '\n' && c != '\r' && ~c)
			x = (x << 1) + (x << 3) + (c ^ 48);
		if (flag)return -x; return x;
	}
	void write(ll x) { if (x < 0)putchar('-'), x = -x; if (x >= 10)write(x / 10); putchar(x % 10 ^ 48); }
}
struct Node {
	int a, b, c, tot = 0, cnt;
	Node() {}
	Node(int c, int b, int a): a(a), b(b), c(c) {}
	bool operator <(const Node s)const { return a < s.a || (a == s.a && (b < s.b || (b == s.b && c < s.c))); }
	bool operator !=(const Node s)const { return a != s.a || b != s.b || c != s.c; }
}a[N], tmp[N], b[N];
int ans[N], n, k, c[N];
void update(int x, int data) {
	while (x <= k) {
		c[x] += data;
		x += lowbit(x);
	}
}
int query(int x) {
	int ans = 0;
	while (x) {
		ans += c[x];
		x -= lowbit(x);
	}
	return ans;
}
void CDQ(Node *p, int len) {
	if (len == 1)return;
	int mid = len >> 1;
	CDQ(p, mid); CDQ(p + mid, len - mid);
	int i = 0, j = mid, k = 0;
	while (i < mid && j < len) {
		if (p[i].b <= p[j].b) {
			update(p[i].c, p[i].cnt);
			tmp[k++] = p[i++];
		}
		else  {
			p[j].tot += query(p[j].c);
			tmp[k++] = p[j++];
		}
	}
	while (j < len) {
		p[j].tot += query(p[j].c);
		tmp[k++] = p[j++];
	}
	for (int t = i - 1; ~t; --t)update(p[t].c, -p[t].cnt);
	while (i < mid)tmp[k++] = p[i++];
	for (int i = 0; i < len; ++i)p[i] = tmp[i];
}

int main(void) {
	//freopen("1.in", "r", stdin);
	int cnt = 0;
	n = fast_IO::read(), k = fast_IO::read();
	for (int i = 1; i <= n; ++i)
		a[i] = Node(fast_IO::read(), fast_IO::read(), fast_IO::read());
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) {
		if (a[i] != a[i - 1])b[++cnt] = a[i], b[cnt].cnt = 1;
		else ++b[cnt].cnt;
	}
	CDQ(b + 1, cnt);
	for (int i = 1; i <= n; ++i)ans[b[i].tot + b[i].cnt - 1] += b[i].cnt;
	for (int i = 0; i < n; ++i)
		printf("%d\n", ans[i]);
	return 0;
}

事实上，CDQ是可以不断套娃的，三维偏序问题还可以通过CDQ套CDQ来解决。
第一层CDQ与上面的过程类似，只不过我们不需要进行树状数组的操作，只是在原来的update和query处打上tag标记，表示这个位置是计入答案或者统计答案。
在排序完成后我们在CDQ内对同一区间进行第二层CDQ，此时的区间是以b为第一关键字，c为第二关键字排序后的结果，因此跟一层CDQ就非常类似的，唯独是在第二层CDQ中计入和统计答案时要注意第一层CDQ中打的标记，比如如果当前左区间的c小于等于右区间的c，但是第一层中并没有给他打标记，就说明当前右区间的元素实际上在第一层时是在左区间，于是就不能进行贡献统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void CDQ2(Node *p, int len) {
	if (len == 1)return;
	int mid = len >> 1;
	CDQ2(p, mid); CDQ2(p + mid, len - mid);
	int i = 0, j = mid, k = 0, sum = 0;
	while (i < mid && j < len) {
		if (p[i].c <= p[j].c) {
			sum += p[i].tag;
			tmp[k++] = p[i++];
		}
		else {
			if (!p[j].tag)tt[p[j].tot] += sum;
			tmp[k++] = p[j++];
		}
	}
	while (j < len) {
		if (!p[j].tag)tt[p[j].tot] += sum;
		tmp[k++] = p[j++];
	}
	while (i < mid)tmp[k++] = p[i++];
	for (int i = 0; i < len; ++i)p[i] = tmp[i];
}
void CDQ(Node *p, int len) {
	if (len == 1)return;
	int mid = len >> 1;
	CDQ(p, mid); CDQ(p + mid, len - mid);
	int i = 0, j = mid, k = 0;
	while (i < mid && j < len) {
		if (p[i].b <= p[j].b)tmp[k] = p[i], tmp[k++].tag = p[i++].cnt;
		else tmp[k] = p[j++], tmp[k++].tag = 0;
	}
	while (j < len)tmp[k] = p[j++], tmp[k++].tag = 0;
	while (i < mid)tmp[k] = p[i], tmp[k++].tag = p[i++].cnt;
	for (int i = 0; i < len; ++i)a[i] = p[i] = tmp[i];
	CDQ2(a, len);
}

以此类推，其实无论多少维的偏序问题我们都可以通过CDQ套娃来解决。

整体二分

咕咕咕