DDOSvoid's Blog

CDQ分治

发表于 更新于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

简介

大概是一种特殊的分治吧

一般可以离线做的题目都可以尝试用 $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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define cQ const Query
#define maxn 500010
using namespace std;

int n, m;

struct Query { 
    int x, v, id;

    Query() {}
    Query(int _x, int _v, int _id) { x = _x; v = _v; id = _id; }

    friend bool operator < (cQ &u, cQ &v) { return u.x < v.x; } 
} Q[maxn * 3]; int cnt;

int ans[maxn], cans;
void cdq(int l, int r) {
    if (l == r) return ; int m = l + r >> 1, j = l - 1, sum = 0;
    cdq(l, m); cdq(m + 1, r); 
    for (int i = m + 1; i <= r; ++i) {
        int x = Q[i].x, v = Q[i].v, id = Q[i].id;
        if (!id) continue;
        while (j < m && Q[j + 1].x <= x) {
            ++j; if (Q[j].id) continue;
            sum += Q[j].v;
        } ans[id] += v * sum; 
    }
    inplace_merge(Q + l, Q + m + 1, Q + r + 1); 
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int x; scanf("%d", &x);
        Q[++cnt] = Query(i, x, 0);
    }
    for (int i = 1; i <= m; ++i) {
        int opt, x, y; scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1) Q[++cnt] = Query(x, y, 0);
        else {
            Q[++cnt] = Query(x - 1, -1, ++cans);
            Q[++cnt] = Query(y, 1, cans);
        }
    } 
    cdq(1, cnt);
    for (int i = 1; i <= cans; ++i) printf("%d\n", ans[i]);
    return 0;
}

例题

  1. 三维偏序

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

  2. 简要题意：给定 $n$ 个思维空间中的点，求一条最长的路径，满足任意一维坐标都是单调不降的

    $n\le 5\times 10^4$

    简要题解：大概就是一个四维偏序

    我们考虑 $cdq$ 套 $cdq$，在内层 $cdq$ 中用树状数组解决二维偏序

    由于计算的是 $dp$ 值，要注意计算贡献和 $cdq$ 的顺序

    至于 $cdq$ 内如何套 $cdq$，大概就是记录一下这个数是左边还是右边的

    时间复杂度 $O(n\log^3 n)$，常数很小

    Luogu P3769 [CH弱省胡策R2]TATT

  3. 简要题意：给定 $n$ 个二维点，现在有 $m$ 次操作，操作有两种，第一种操作是加入一个二维点 $(x_i,y_i)$；第二种操作给定一个二维点 $(x_i,y_i)$ 求离它最近的点与它的距离

    $n\le 3\times 10^5$

    简要题解：变换坐标后做四次 $cdq$ 分治就行了

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

  4. 简要题意：给定 $n$ 个物品和 $m$ 个属性以及常数 $w$，第 $i$ 个物品有一个价值 $c_i$ 以及其所拥有的属性 $S_i$，现在要依次选择若干个物品，满足相邻两个物品 $i$ 和 $j$ 满足 $i<j\wedge w+c_i\ge c_j\wedge S_i\subseteq S_j$，求最多选择多少个物品

    $n\le 10^5,m\le 18$

    简要题解：首先考虑 $cdq$ 分治解决第一个和第二个限制，对于第三个限制，我们考虑每次 $cdq$ 分治的时候将左部的每个点都贡献到自己的超集，这样可以做到 $O(2^m)$ 预处理，$O(1)$ 查询，或者我们考虑用右部的每个点求子集查询，这样是 $O(1)$ 预处理，$O(2^m)$ 查询，我们可以平衡一下，前 $\frac m 2$ 位贡献到超集，后 $\frac m 2 $ 子集查询，这样做的时间复杂度为 $O(2^{\frac m 2}n\log n+n\log^2 n)$

    Luogu P7842 「C.E.L.U-03」探险者笔记 III