【学习笔记】CDQ分治

大概是对操作分治的算法,算是我最早学过的离线分治算法了?

大题思想就是考虑对操作分治,每次统计左边一半的修改对右边询问的影响,类似于二进制拆分,使得每个询问的答案统计可以分成不同的几块。

那么复杂度就是 $T(n)=2T(\frac{n}{2})+O(n\log^kn)$ ,解得 $T(n)=O(n\log ^{k+1}n)$ 。

loj#112 [模板]三维偏序

有 $n$ 个元素,第 $i$ 个元素有 $a_i$、$b_i$、$c_i$三个属性。

设 $f_i$ 表示满足 $a_j\leq a_i$ 且 $b_j\leq b_i$ 且 $c_j\leq c_i$ 的 $j$ 的数量。

对于 $\forall i \in [0,n)$ ,求 $f_j=i$ 的 $j$ 的数量。

这不是传统意义上的 $\rm CDQ$ 。考虑 $\rm CDQ$ 在维护本质上是在维护一系列权值,通过分治统计前面对后面的贡献,类似于通过分治对全局的询问做时间上的二进制拆分。所以其实具有类似拆分性质的统计都可以这么实现。

回到这题,发现本质上三维数点也可以直接通过 $\rm CDQ$ 解决。考虑在分治完后,需要统计本层左区间对右区间的贡献。这时直接bit+扫描线即可,即按照一维排序,另一维用bit维护。

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
#define il inline
#define LL long long

#define MAXN 200010
#define low(x) (x & (-x))

using namespace std ;
int N, K, bit[MAXN], res[MAXN] ;
struct nodes{ int x, y, z, ans ; }base[MAXN], t[MAXN] ;
il bool operator == (nodes a, nodes b){
return (a.x == b.x) & (a.y == b.y) & (a.z == b.z) ;
}
il int qr(){
char c = getchar() ; int res = 0, fg = 1 ;
while (!isdigit(c)) { if (c == '-') fg = -1 ; c = getchar() ;}
while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar() ;
return res * fg ;
}
il bool comp1(nodes a, nodes b){
return a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x < b.x ;
}
il bool comp2(nodes a, nodes b){
return a.y == b.y ? a.z < b.z : a.y < b.y ;
}
il void upd(int p, int v){
for ( ; p <= K ; p += low(p)) bit[p] += v ;
}
il int qry(int p){
int ret = 0 ;
for ( ; p ; p -= low(p)) ret += bit[p] ;
return ret ;
}
void cdq(int L, int R){
if (L >= R) return ;
int Mid = (L + R) >> 1, l, r ;
cdq(L, Mid), cdq(Mid + 1, R) ;
sort(base + L, base + Mid + 1, comp2), l = L ;
sort(base + Mid + 1, base + R + 1, comp2), r = Mid + 1 ;
while (r <= R){
while (l <= Mid && base[l].y <= base[r].y)
upd(base[l].z, 1), ++ l ;
base[r].ans += qry(base[r].z), ++ r ;
}
for (int i = L ; i < l ; ++ i) upd(base[i].z, -1) ;
}
int main(){
cin >> N >> K ; int i, j, o ;
for (i = 1 ; i <= N ; ++ i)
base[i].x = qr(), base[i].y = qr(), base[i].z = qr() ;
sort(base + 1, base + N + 1, comp1) ; cdq(1, N) ;
sort(base + 1, base + N + 1, comp1) ;
for (i = 1, j = o = 0 ; i <= N ; j = o = 0){
while (base[i] == base[i - 1]) ++ i, ++ j ;
for (int k = i - j - 1 ; k < i ; ++ k) o = max(o, base[k].ans) ;
for (int k = i - j - 1 ; k < i ; ++ k) base[k].ans = o ; if (!j) ++ i ;
}
for (i = 1 ; i <= N ; ++ i) res[base[i].ans] ++ ;
for (i = 0 ; i < N ; ++ i) printf("%d\n", res[i]) ;
return 0 ;
}

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

给定一张 $n\times m$ 的网格。

有两个操作,插入一个新的点或者询问离某个点欧几里得距离最近的点。

$n,m\leq 3\times10^5$

发现欧几里得距离即:

通过分类讨论可以得到有这么四类情况:

发现,其中第二种情况就是第一种按照 $x$ 轴对称了一下的结果,后两种类似。于是可以通过坐标变换都转化到第一种问题。

对于第一个问题,发现询问可以分段处理,于是想到 $\rm CDQ$ 。考虑如何处理离自己最近的点:

这样转化出来的两部分即具有差分性质(即可以拆),并且保证了只与时间轴有关(不再和网格图有关)。所以可以把 $x_i+y_i$ 插入进去,这样就可以用四遍 $\rm CDQ$ 做完这题了。

感觉还是很神仙的吧…

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
#define il inline
#define rg register
#define LL long long
#define MAXN 600010
#define MAXM 2000010
#define Inf 192608170
#define low(x) (x & (-x))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

using namespace std ;
int N, M, K, bit[MAXM], ans[MAXN] ;
struct qrys{ int mk, id, x, y ; }t[MAXN], q[MAXN], base[MAXN] ;

#define ch_top 24000001
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;

il int read(){
while (*++now_r < 48) ;
register int x = *now_r - 48 ;
while (*++now_r >= 48) x = (x << 1) + (x << 3) + *now_r - 48 ;
return x ;
}
il void write(int x){
static char st[7] ; static int top ;
while (st[++ top] = 48 + x % 10, x /= 10) ;
while (*++ now_w = st[top], -- top) ; *++ now_w = '\n' ;
}
il void del(int p){
for ( ; p <= K && bit[p] ; p += low(p)) bit[p] = 0 ;
}
il void upd(int p, const int &v){
for ( ; p <= K ; p += low(p)) bit[p] = max(bit[p], v) ;
}
il int qry(int p){
rg int ret = 0 ;
for ( ; p ; p -= low(p)) ret = max(ret, bit[p]) ;
return ret ? ret : -Inf ;
}
void cdq(int L, int R){
if (L == R) return ;
rg int Mid = (L + R) >> 1, l, r, o = L ;
cdq(L, Mid), cdq(Mid + 1, R), l = L, r = Mid + 1 ;
while (r <= R){
while (l <= Mid && base[l].x <= base[r].x){
if (base[l].mk < 2)
upd(base[l].y, base[l].x + base[l].y) ;
t[o ++] = base[l ++] ;
}
if (base[r].mk > 1)
ans[base[r].id] = min(ans[base[r].id],
base[r].x + base[r].y - qry(base[r].y)) ;
t[o ++] = base[r ++] ;
}
for (rg int i = L ; i < l ; ++ i)
if (base[i].mk < 2) del(base[i].y) ;
while (l <= Mid) t[o ++] = base[l ++] ;
for (rg int i = L ; i <= R ; ++ i) base[i] = t[i] ;
}
void solve(const int &ox, const int &oy){
for (rg int i = 1 ; i <= N + M ; ++ i){
base[i] = q[i] ;
base[i].x = ox ? q[i].x : K - q[i].x,
base[i].y = oy ? q[i].y : K - q[i].y ;
}
cdq(1, N + M) ;
}
int main(){
// freopen("data1.in", "r", stdin) ;
// freopen("data1.out", "w", stdout) ;
fread(ch, 1, ch_top, stdin) ;
N = read(), M = read() ; int i ;
memset(ans, 63, sizeof(ans)) ;
for (i = 1 ; i <= N ; ++ i)
q[i].mk = 1, q[i].id = i, q[i].x = read() + 1,
q[i].y = read() + 1, K = max(K, max(q[i].x, q[i].y) + 1) ;
for (i = N + 1 ; i <= N + M ; ++ i)
q[i].mk = read(), q[i].id = i, q[i].x = read() + 1,
q[i].y = read() + 1, K = max(K, max(q[i].x, q[i].y) + 1) ;
solve(1, 0), solve(0, 1), solve(1, 1), solve(0, 0) ;
for (i = N + 1 ; i <= N + M ; ++ i) if (q[i].mk > 1) write(ans[i]) ;
fwrite(ch, 1, now_w - ch, stdout) ; return 0 ;
}

[Baltic OI 2008]Mokia

维护一个 $w\cdot w$ 的矩阵,支持:

1、单点加。

2、子矩阵查询。

$w\leq 2\cdot 10^6,q\leq 3\cdot 10^5$ 。

考虑把询问按照二维前缀和拆成四个之后就可以直接 BIT 做了。于是就直接cdq。但是发现时间这一维本来就是有序的,所以可以在分治的每一层里面按时间回答完询问之后,将两半按 $x$ 归并起来,就可以省下 sort 了。不过即使这样复杂度还是 $O(n\log n\log m)$ 的,虽然确实快了一倍左右。

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
//普通版本
struct qss{
int id ;
int res ;
int x, y ;
int isq, val ;
qss (int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0){
id = a, x = b, y = c, isq = d, val = e, res = f ;
}
}qs[N] ;

int m, n ;
int _bit[M] ;

#define low(x) (x & -x)

void ins(int p, int x){
for ( ; p <= m ; p += low(p)) _bit[p] += x ;
}
int qry(int p){
int ret = 0 ;
for ( ; p ; p -= low(p)) ret += _bit[p] ;
return ret ;
}

int xl, yl, xr, yr, v, mk, Id ;

bool comp_Id(const qss &a, const qss &b){ return a.id < b.id ; }

bool comp_co(const qss &a, const qss &b){ return a.x == b.x ? a.y < b.y : a.x < b.x ; }

void cdq(int l, int r){
if (l == r) return ;
int mid = (l + r) >> 1 ;
int tl = l, tr = mid + 1 ;
cdq(l, mid) ; cdq(mid + 1, r) ;
sort(qs + l, qs + mid + 1, comp_co) ;
sort(qs + mid + 1, qs + r + 1, comp_co) ;
while (tr <= r){
while (tl <= mid && qs[tl].x <= qs[tr].x){
if (!qs[tl].isq) ins(qs[tl].y, qs[tl].val) ; ++ tl ;
}
if (qs[tr].isq) qs[tr].res += qry(qs[tr].y) ; ++ tr ;
}
for (int i = l ; i < tl ; ++ i)
if (!qs[i].isq) ins(qs[i].y, - qs[i].val) ;
}

int main(){
cin >> mk >> m ; ++ m ;
while (scanf("%d", &mk) != EOF){
if (mk == 3) break ;
if (mk == 1){
xl = qr() + 1, yl = qr() + 1, v = qr() ;
++ Id ; qs[++ n] = qss(Id, xl, yl, 0, v, 0) ;
}
else {
xl = qr() + 1, yl = qr() + 1 ;
xr = qr() + 1, yr = qr() + 1 ;
++ Id ; qs[++ n] = qss(Id, xr, yr, 1, 1, 0) ;
++ Id ; qs[++ n] = qss(Id, xl - 1, yr, 1, -1, 0) ;
++ Id ; qs[++ n] = qss(Id, xr, yl - 1, 1, -1, 0) ;
++ Id ; qs[++ n] = qss(Id, xl - 1, yl - 1, 1, 1, 0) ;
}
}
cdq(1, n) ; int ans ;
sort(qs + 1, qs + n + 1, comp_Id) ;
for (int i = 1 ; i <= n ; ){
if (!qs[i].isq) { ++ i ; continue ;} ans = 0 ;
for (int j = 0 ; j < 4 ; ++ j)
ans += qs[i + j].val * qs[i + j].res ;
printf("%d\n", ans) ; i += 4 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//归并版本
void cdq(int l, int r){
if (l == r) return ;
int mid = (l + r) >> 1 ;
int tl = l, tr = mid + 1 ;
cdq(l, mid) ; cdq(mid + 1, r) ;
while (tr <= r){
while (tl <= mid && qs[tl].x <= qs[tr].x){
if (!qs[tl].isq) ins(qs[tl].y, qs[tl].val) ; ++ tl ;
}
if (qs[tr].isq) qs[tr].res += qry(qs[tr].y) ; ++ tr ;
}
for (int i = l ; i < tl ; ++ i)
if (!qs[i].isq) ins(qs[i].y, - qs[i].val) ;
tl = l, tr = mid + 1 ; int tot = 0 ;
while (tl <= mid || tr <= r){
if (tl <= mid && tr <= r && qs[tl].x <= qs[tr].x) tmp[++ tot] = qs[tl], ++ tl ;
else if (tr <= r && tl <= mid && qs[tl].x >= qs[tr].x) tmp[++ tot] = qs[tr], ++ tr ;
else if (tl <= mid) tmp[++ tot] = qs[tl], ++ tl ; else if (tr <= r) tmp[++ tot] = qs[tr], ++ tr ;
}
for (int i = l ; i <= r ; ++ i) qs[i] = tmp[i - l + 1] ;
}

后记

不知道啥时候才能真正地灵活运用…