Theme NexT works best with JavaScript enabled

从偏序问题到 CDQ 分治

本文是南邮 ICPC 校队暑期集训第一次讲座的课件的整理。

前置知识

树状数组

树状数组是一种用于维护区间的数据结构,支持单点修改和区间查询。其核心思想如下:

令 $lowbit(i)$ 表示整数 $i$ 的二进制表示中,最低位的 $1$ 代表的数。如:$lowbit(6)=2,lowbit(7)=1,lowbit(8)=8$

定义数组 $c$,令 $c[i]$ 表示 $a$ 数组区间 $(i-lowbit(i),i]$ 内的元素和。如:$c[6]=\sum_{i=5}^6 a[i], c[7]=\sum_{i=7}^7a[i], c[8]=\sum_{i=1}^8 a[i]$。

为后文方便表示,我们记 $f(x)=x-lowbit(x)$,$f^k(x)=f(f^{k-1}(x))$。

这样,当我们想要查询区间 $[1,x]$ 内的元素和时。我们只需要查询 $c[x]+c[f(x)]+c[f^2(x)]+\dots +c[f^k(x)]$ 。

由于每次 $x$ 变成 $f(x)$,都会有一个二进制位的 $1$ 变成 $0$,而 $x$ 的二进制表示中最多只有 $\log_2(x)$ 个 $1$,因此 $k \leq \log_2(x)$,即单次查询时间复杂度为 $O(\log n)$。

对于修改,我们可以用同样的方法证明它的时间复杂度是 $O(\log n)$。

定义

下面内容节选自中文维基

偏序集合是数学中,特别是序理论中,指配备了部分排序关系的集合。 这个理论将排序、顺序或排列这个集合的元素的直觉概念抽象化。这种排序不必然需要是全部的,就是说不必要保证此集合内的所有对象的相互可比较性。

给定集合 $S$,$\leq$ 是 S 上的二元关系,若 $≤$ 满足:

  1. 自反性:$\forall a \in S$,有 $a \leq a$;
  2. 反对称性:$\forall a,b \in S$,$a \leq b$ 且 $b \leq a$,则 $a=b$;
  3. 传递性:$\forall a,b,c \in S$,$a \leq b$ 且 $b \leq c$,则 $a \leq c$;

则称 $\leq$ 是 $S$ 上的非严格偏序自反偏序

给定集合 $S$,$<$ 是 $S$ 上的二元关系,若 $<$ 满足:

  1. 反自反性:$\forall a \in S$,有 $a\not< a$;
  2. 非对称性:$ \forall a,b \in S$,$a<b \Rightarrow b \not< a$;
  3. 传递性:$\forall a,b,c \in S$,$a<b$ 且 $b<c$,则 $a<c$;

则称 $<$ 是 $S$ 上的严格偏序反自反偏序

一般的说偏序集合的两个元素 $x$ 和 $y$ 可以处于四个相互排斥的关联中任何一个:要么 $xy$,要么 $x$ 和 $y$ 是不可比较的(三个都不是)。

全序集合是用规则排除第四种可能的集合:所有元素对都是可比较的,并且声称三分法成立。自然数、整数、有理数和实数都关于它们代数(有符号)大小是全序的,而复数不是。这不是说复数不能全序排序;比如我们可以按词典次序排序它们,通过 $x + iy < u + iv$ 当且仅当 $x<u$ 或($x=u$ 且 $y<v$),但是这种排序没有合理的大小意义因为它使得 $1$ 大于 $100i$。按绝对大小排序它们产生在其中所有对都是可比较的预序,但这不是偏序因为 $1$ 和 $i$ 有相同的绝对大小但却不相等,违反了反对称性。

简单地说,偏序关系就是集合内只有部分元素之间在这个关系下可以比较,全序关系就是集合内任何一对元素在在这个关系下都相互可比较。

算法竞赛中常见的偏序问题正是描述了一种逻辑简单的偏序关系。

偏序问题

算法竞赛中的偏序问题一般如下格式:

对于 $k$ 维偏序问题,首先定义一个 $k$ 元组:$\{a,b,c ,\dots \}$,令 $a(i)$ 表示 $k$ 元组中的第 $i$ 个元素。并规定一个偏序关系 $\oplus$,我们称 $a\oplus b$ 当且仅当 $\forall i \in[1,n]$ 且 $i \in Z$ ,有 $a(i) < b(i)$。现给定你一个 $k$ 元组多重集,并指定一个 $k$ 元组 $a$,询问你多重集中有多少个元素与其满足偏序关系。

一个经典的偏序问题的例子是逆序对:

给定一个长度为 $n$ 的整数序列 $a$ ,询问序列中有多少对元素满足 $a_i > a_j$ 且 $i<j$。

这里我们将序列中每个元素的下标也作为该元素的一部分,这样该整数序列就变成了一个二元组多重集,元素的值和下表共同构成一个二元组。这样这道题就成为了二维偏序问题。询问的是多重集中满足偏序关系的元素对的数量,实际上就是指定每一个多重集中元素,询问你多重集中有多少个元素与其满足偏序关系,这 $n$ 次询问的答案总和即为逆序对的个数。

下面我们将介绍对于不同维度的偏序问题,我们应该如何处理。

一维偏序问题

一维偏序问题较为特殊,因为一维偏序实质上是全序的,我们只需要排序即可。

预处理时间复杂度 $O(n \log n)$。

查询时间复杂度 $O(1)$。

二维偏序问题

二维偏序问题一般使用树状数组实现。

思路如下,既然要求对于给定的 $b$,满足 $a<b$ 的 $a$ 的数量。那么有 $a(1)<b(1)$ 且 $a(2)<b(2)$。

我们对这些元素按照第一维大小关系排序,那么对于元素 $a_i$,若有 $a_j<a_i$,则有 $j<i$,我们只需要查询满足 $a_j(2)<a_i(2)$ 的 $j~(1 \leq j < i)$ 的数量。

这样,我们使用树状数组对元素值对区间 $[1,i)$ 内的元素值进行统计,对于每一个 $j \in [1,i)$ 我们让数组中下标为 $a_j(2)$ 的位置对应的值 $+1$。当我们查询数组中区间 $[1,a_i(2))$ 的元素和,我们就知道序列中有多少 $j$ 满足 $a_i(2)<a_i(2)$。

预处理时间复杂度 $O(n \log n)$。

单次查询平均时间复杂度 $O(\log n)$。

三维偏序问题

三维偏序问题一般采用 CDQ 分治解决。

CDQ 分治来源于 09 年知名 OI 选手陈丹琦的国家队论文,其主要流程如下:

首先对全部元素按照第一维升序排序。

每一层 CDQ 中,我们首先递归处理左右区间,然后统计左区间对右区间的贡献(右区间对左区间无贡献,因为右区间的元素的第一维均大于左区间的元素第一维),然后将左右区间排序(按照第二维大小升序排序)。

注意到我们是首先递归左右区间,因此当我们开始处理当前区间中左区间对右区间的贡献时,左右区间均已按照第二维大小升序排列,这样我们枚举右区间的每一个元素,统计左区间中有多少数小于它,使用的方法和树状数组求解二维偏序问题相同。

预处理时间复杂度 $O(n \log n)$。

单次查询平均时间复杂度 $O(\log^2 n)$。

四维偏序问题

使用的方法为 CDQ 分治套 CDQ 分治,思路与三维偏序相同。

预处理时间复杂度 $O(n \log n)$。

单次查询平均时间复杂度 $O(\log^3 n)$。

动态 $k$ 维偏序问题

动态指增加操作和查询操作有时间的先后,这样只要把时间作为第 $k+1$ 维,该问题即变为静态第 $k+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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200001
struct use {
int x, y, z, f, index;
} a[N << 1], t[N << 1];
int n, m, x, y, z, cnt, sum;
int ans[N], c[N];
int lowbit(int h) { return h & -h; }
void add(int h, int x) {
for (int i = h; i < N; i += lowbit(i)) c[i] += x;
}
int query(int h) {
int tmp = 0;
for (int i = h; i; i -= lowbit(i)) tmp += c[i];
return tmp;
}
bool cmp(use x, use y) {
if (x.z != y.z) return x.z < y.z;
if (x.y != y.y) return x.y < y.y;
if (x.x != y.x) return x.x < y.x;
return x.index < y.index;
}
void CDQ(int l, int r) {
int mid = (l + r) >> 1;
if (l != mid) CDQ(l, mid);
if (mid + 1 != r) CDQ(mid + 1, r);
//----
int p = l, q = mid + 1, tot = l;
while (p <= mid && q <= r) {
if (a[p].x <= a[q].x) {
if (!a[p].index) add(a[p].y, a[p].f);
t[tot++] = a[p++];
} else {
if (a[q].index) ans[a[q].index] += query(a[q].y);
t[tot++] = a[q++];
}
}
while (q <= r) {
if (a[q].index) ans[a[q].index] += query(a[q].y);
t[tot++] = a[q++];
}
for (int i = l; i <= p - 1; i++)
if (!a[i].index) add(a[i].y, -a[i].f);
while (p <= mid) t[tot++] = a[p++];
for (int i = l; i <= r; i++) a[i] = t[i];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int x, y, z, w;
scanf("%d%d%d%d", &x, &y, &z, &w);
a[++cnt] = use{x, y, z, w, 0};
}
for (int i = 1; i <= m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
a[++cnt] = use{x, y, z, 0, i};
}
sort(a + 1, a + cnt + 1, cmp);
CDQ(1, cnt);
for (int i = 1; i <= m; i++) printf("%d\n", (ans[i]));
return 0;
}