Some examples of “CDQ Divide and Conquer” algorithm

2021/02/09

What is CDQ D&C?

CDQ D&C is a offline technique invented by a China competitive programmer (called CDQ, obviously). CDQ D&C is almost same to normal D&C. The biggest difference between them is that suppose we cut a interval \([l,r)\) into \([l,m)\),\([m,r)\). In normal D&C, the elements from \([l,m)\) won’t influence \([m,r)\); In CDQ D&C, elemenst from \([l,m)\) will influence \([m,r)\). ——robert1003

引入:三维偏序问题

给定 \(n\) 个元素(编号 \(1 \sim n\)),其中第 \(i\) 个元素具有 \(a_i,b_i,c_i\) 三种属性。 设 \(f(i)\) 表示满足以下 \(4\) 个条件:

\(a_j \le a_i, \quad b_j \le b_i, \quad c_j \le c_i, \quad j \neq i\)

的 \(j\) 的数量。对于 \(d \in [0,n)\),求满足 \(f(i) = d\) 的 \(i\) 的数量。

输入格式:

第一行两个整数 \(n,k\),表示元素数量和最大属性值。

接下来 \(n\) 行,其中第 \(i\) 行包含三个整数 \(a_i,b_i,c_i\),分别表示第 \(i\) 个元素的三个属性值。

输出格式:

共 \(n\) 行,每行输出一个整数,其中第 \(d + 1\) 行的整数表示满足 \(f(i) = d\) 的 \(i\) 的数量。

数据范围:

\(1 \le n \le 10^5\)

\(1 \le a_i,b_i,c_i \le k \le 2 \times 10^5\)

输入样例:

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

输出样例:

3
1
3
0
1
0
1
0
0
1

思路:

这是 \(CDQ\) 分治的模板题,此分治算法的时间复杂度为 \(O(N \times (logN)^2)\)

假设三维元素为 \(a,b,c\), 那么第一维直接排序 \(a\), 第二维归并排序 \(b\),第三维用树状数组存储 \(c\)。

每次归并用左边一半来进行树状数组的 \(add\) 操作,右边一半来 \(query\) 查询更新答案。

细节处理的地方就是相同的元素,元素相同是指三维全部相同,那么需要去重,然后记录每一个相同元素的个数。 每次 \(add\) 操作的个数就是所有该元素的个数,最后求得的答案也要加上相同元素的个数。

模板:

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 200010;

int n, m;
struct Data {
    int a, b, c, s, res;
    bool operator< (const Data& t) const {
        if (a != t.a) return a < t.a;
        if (b != t.b) return b < t.b;
        return c < t.c;
    }
    bool operator== (const Data& t) const {
        return a == t.a && b == t.b && c == t.c;
    }
} q[N], w[N]; //w[]归并的临时数组

int tr[M], ans[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int v) {
    for (int i = x; i < M; i += lowbit(i)) tr[i] += v;
}

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        //左一半来add  右一半来查询答案
        if (q[i].b <= q[j].b) add(q[i].c, q[i].s), w[k++] = q[i++];
        //如果左边的q[i].b比右边的q[j].b大 因为左边的b已经有序了,所以i后边的b肯定比q[j].b都大
        //此时q[j]就可以求出符合小于c的元素个数了
        else q[j].res += query(q[j].c), w[k++] = q[j++];

    //扫描剩下的元素
    while (i <= mid) add(q[i].c, q[i].s), w[k++] = q[i++];
    while (j <= r) q[j].res += query(q[j].c), w[k++] = q[j++];
    for (int i = l; i <= mid; i++) add(q[i].c, -q[i].s);  //每次递归一层结束将左边add的树状数组清空
    for (int i = l, j = 0; j < k; i++, j++) q[i] = w[j];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        q[i] = {a, b, c, 1};
    }
    sort(q, q + n);
    int k = 1;
    for (int i = 1; i < n; i++) //去重 记录相同元素的数量
        if (q[i] == q[k - 1]) q[k - 1].s++;
        else q[k++] = q[i];

    merge_sort(0, k - 1);
    for (int i = 0; i < k; i++)
        //res存去重之后的结果,还要加上相同的配对的s-1个
        ans[q[i].res + q[i].s - 1] += q[i].s;

    for (int i = 0; i < n; i++) printf("%d\n", ans[i]);

    return 0;
}

 

CQOI2017《老C的任务》

题目描述:

老 \(C\) 是个程序员。最近老 \(C\) 从老板那里接到了一个任务——给城市中的手机基站写个管理系统。

作为经验丰富的程序员,老 \(C\) 轻松地完成了系统的大部分功能,并把其中一个功能交给你来实现。

由于一个基站的面积相对于整个城市面积来说非常的小,因此每个的基站都可以看作坐标系中的一个点,其位置可以用坐标 \((x,y)\) 来表示。

此外,每个基站还有很多属性,例如高度、功率等。

运营商经常会划定一个区域,并查询区域中所有基站的信息。

现在你需要实现的功能就是,对于一个给定的矩形区域,回答该区域中(包括区域边界上的)所有基站的功率总和。

如果区域中没有任何基站,则回答 \(0\)。

输入格式:

第一行两个整数 \(n,m\),表示一共有 \(n\) 个基站和 \(m\) 次查询。

接下来一共有 \(n\) 行,每行由 \(x_i , y_i , p_i\) 三个空格隔开的整数构成,表示一个基站的坐标 \((x_i, y_i)\) 和功率 \(p_i\)。不会有两个基站位于同一坐标。

接下来一共有 \(m\) 行,每行由 \(x_{1j},y_{1j},x_{2j},y_{2j}\) 四个空格隔开的整数构成,表示一次查询的矩形区域。该矩形对角坐标为 \((x_{1j} , y_{1j})\) 和 \((x_{2j} , y_{2j})\),且 \(4\) 边与坐标轴平行。

输出格式:

输出 \(m\) 行,每行一个整数,对应每次查询的结果。

数据范围:

\(1 \le n,m \le 10^5\)

\(-2^{31} ≤ x_i,y_i,p_i,x_{1j},y_{1j},x_{2j},y_{2j} < 2^{31}\)

\(x_{1j} ≤ x_{2j}, y_{1j} ≤ y_{2j}\)

输入样例:

4 2
0 0 1
0 1 2
2 2 4
1 0 8
0 0 1 1
1 1 5 6

输出样例:

11
4

思路:

将所有询问和原图中的点一起处理,用变量 \(z\) 标记区分, \(0\) 代表原图的点, \(1\)是询问的点,

对于每个询问的点 \((a_i,a_j)\) 就是询问有多少点符合 \(b_i \le a_i, b_j \le a_j, z_j < z_i\), 则转化为三维偏序。

用二维前缀和存每个矩阵内的元素和,标记 \(sign\) 为每个询问里面加上还是减去该矩阵求出子矩阵, 用 \(id\) 来表示询问的编号,这样才能同时处理加和减的操作,因为所有的操作都在一个数组中。

此题由于只有原图的点和询问的点,也就意味着第三维变量的个数只有两个,所以不用树状数组,直接用变量 \(sum\) 存左半边的结果来更新右边即可,所以此题使用 \(CDQ\) 分治复杂度 \(O(N \times logN)\)。

这类问题也可用专门解决高维查询的数据结构 \(KD-Tree\)1 解决, 另外,此题用 \(CDQ\) 分治不需要处理元素相同的情况, 因为 \(z\) 维不相同。

代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 500010; // N + 4 * M

int n, m;

struct Data {
    int x, y, z, p, id, sign; //z=0表示原图的点 1代表查询 p是点权 id是查询id sign加减符号
    ll sum;

    bool operator< (const Data&  t) const {
        if (x != t.x) return x < t.x;
        if (y != t.y) return y < t.y;
        return z < t.z;
    }
} q[N], w[N]; //w辅助数组

ll ans[N];

void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    ll sum = 0;
    while (i <= mid && j <= r)
        //直接用sum来存即可 只有0/1两种情况
        if (q[i].y <= q[j].y) sum += !q[i].z * q[i].p, w[k++] = q[i++];
        else q[j].sum += sum, w[k++] = q[j++];
    while (i <= mid) sum += !q[i].z * q[i].p, w[k++] = q[i++];
    while (j <= r) q[j].sum += sum, w[k++] = q[j++];
    for (int i = l, j = 0; j < k; i++, j++) q[i] = w[j];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        int x, y, p;
        scanf("%d%d%d", &x, &y, &p);
        q[i] = {x, y, 0, p};
    }
    int k = n; //将询问也存进q[]
    for (int i = 1; i <= m; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        q[k++] = {x2, y2, 1, 0, i, 1};
        q[k++] = {x1 - 1, y2, 1, 0, i, -1}; //减去的矩形
        q[k++] = {x2, y1 - 1, 1, 0, i, -1};
        q[k++] = {x1 - 1, y1 - 1, 1, 0, i, 1};
    }

    sort(q, q + k);
    merge_sort(0, k - 1);

    for (int i = 0; i < k; i++)
        if (q[i].z)
            ans[q[i].id] += q[i].sum * q[i].sign;

    for (int i = 1; i <= m;  i++) printf("%lld\n", ans[i]);
    return 0;
}

 

CQOI2011《动态逆序对》

题目描述:

对于序列 \(A\),它的逆序对数定义为满足 \(i < j\),且 \(A_i > A_j\) 的数对 \((i,j)\) 的个数。

给 \(1\) 到 \(n\) 的一个排列,按照某种顺序依次删除 \(m\) 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

输入格式:

第一行包含两个整数 \(n\) 和 \(m\),即初始元素的个数和删除的元素个数。

以下 \(n\) 行每行包含一个 \(1\) 到 \(n\) 之间的正整数,即初始排列。

以下 \(m\) 行每行一个正整数,依次为每次删除的元素。

输出格式:

输出包含 \(m\) 行,依次为删除每个元素之前,逆序对的个数。

数据范围:

\(1 ≤ n ≤ 10^5\),

\(1 ≤ m ≤ 50000\)

输入样例:

5 4
1
5
3
4
2
5
1
4
2

输出样例:

5
2
2
1

样例解释:

给定序列变化依次为 \((1,5,3,4,2)→(1,3,4,2)→(3,4,2)→(3,2)→(3)\)。

思路:

首先第一维是不用管的,默认就是初始序列的元素下标 \(i, j\)。

第二维就是元素的值 \(a[i], a[j]\)。

第三维设为删除元素的时间戳,从大到小分配时间戳,因为这样便于树状数组求前缀和。

此题比较特殊,因为逆序对有 \(2\) 种:

$$ \begin{cases} i < j, & a[i] > a[j] \\ i > j, & a[i] < a[j] \end{cases} $$

所以分治时候要分两种情况求出来,一种是左半区间更新右边,一种是右边更新左边。

对于每个元素,当前时间戳需要求出依然存在的元素和该元素互为逆序对的元素数量,然后求前缀和即可。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100010;

int n, m;
struct Data {
    int a, t, res;
} q[N], w[N];

int tr[N], pos[N];
ll ans[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int v) {
    for (int i = x; i < N; i += lowbit(i)) tr[i] += v;
}

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);

    //第一种逆序 左边更新右边
    int i = mid, j = r;
    while (i >= l && j > mid)
        if (q[i].a > q[j].a) add(q[i].t, 1), i --;
        else q[j].res += query(q[j].t - 1), j --;
    while (j > mid) q[j].res += query(q[j].t - 1), j --;
    for (int k = i + 1; k <= mid; k++) add(q[k].t, - 1);

    //第二种逆序 用右边更新左边
    j = l, i = mid + 1;
    while (j <= mid && i <= r)
        if (q[i].a < q[j].a) add(q[i].t, 1), i++;
        else q[j].res += query(q[j].t - 1), j++;
    while (j <= mid) q[j].res += query(q[j].t - 1), j++;
    for (int k = mid + 1; k < i; k++) add(q[k].t, -1);

    //归并
    i = l, j = mid + 1;
    int k = 0;
    while (i <= mid && j <= r)
        if (q[i].a <= q[j].a) w[k ++ ] = q[i ++ ];
        else w[k ++ ] = q[j ++ ];
    while (i <= mid) w[k ++ ] = q[i ++ ];
    while (j <= r) w[k ++ ] = q[j ++ ];

    for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &q[i].a);
        pos[q[i].a] = i;
    }
    for (int i = 0, j = n; i < m; i++) {
        int a;
        scanf("%d", &a);
        q[pos[a]].t = j --; //逆序分配时间戳
        pos[a] = -1;
    }
    for (int i = 1, j = n - m; i <= n; i++) {
        if (pos[i] != -1)
            q[pos[i]].t = j --;
    }

    merge_sort(0, n - 1);

    for (int i = 0; i < n; i++) ans[q[i].t] = q[i].res;
    for (int i = 2; i <= n;  i++) ans[i] += ans[i - 1]; //ans是当前存在的和q[i].a互为逆序对的个数
    for (int i = 0, j = n; i < m; i++, j --) printf("%lld\n", ans[j]);

    return 0;
}

参考: