CDQ 分治

三维偏序类

洛谷 P3810. 三维偏序模板

一共有 $n$ 个对象，属性值范围 $[1,k]$，每个对象有 $a$ 属性、$b$ 属性、$c$ 属性

$f(i)$ 表示，$a_j\le a_i$ 且 $b_j\le b_i$ 且 $c_j\le c_i$ 且 $j\ne i$ 的 $j$ 的数量

$ans(d)$ 表示，$f(i)=d$ 的 $i$ 的数量

打印所有的 $ans[d]$，$d$ 的范围 $[0,n)$

$1\le n\le {10}^5$

$1\le k\le 2\times {10}^5$

分析

代码实现

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

const int N = 1e5 + 10, M = 2e5 + 10;
struct Node {
    int id, a, b, c;
} e[N];
int c[M];
int n, k, f[N], ans[N];

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

void add(int x, int y) {
    for (int i = x; i <= k; i += lowbit(i)) c[i] += y;
}

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

bool cmp(const Node& x, const Node& y) {
    if (x.a != y.a) return x.a < y.a;
    if (x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}

bool cmpB(const Node& x, const Node& y) {
    return x.b < y.b;
}

void cdq(int l, int r) {
    if (l == r) return ;

    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);

    int p1 = l - 1, p2 = mid + 1;
    for (; p2 <= r; p2++) {
        while (p1 + 1 <= mid && e[p1 + 1].b <= e[p2].b) {
            p1 ++;
            add(e[p1].c, 1);
        }
        f[e[p2].id] += query(e[p2].c);
    }

    for (int i = l; i <= p1; i++) add(e[i].c, -1);

    sort(e + l, e + r + 1, cmpB);
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int a, b, c; cin >> a >> b >> c;
        e[i] = {i, a, b, c};
    }

    sort(e + 1, e + 1 + n, cmp);
    for (int l = 1, r = 1; l <= n; ) {
        while (r + 1 <= n && e[l].a == e[r + 1].a && e[l].b == e[r + 1].b && e[l].c == e[r + 1].c) {
            r++;
        }
        for (int i = l; i <= r; i++) {
            f[e[i].id] = r - i;
        }
        l = ++r;
    }

    cdq(1, n);
    for (int i = 1; i <= n; i++) ans[f[i]]++;

    for (int i = 0; i < n; i++) cout << ans[i] << endl;

    return 0;
}

洛谷 P3157. 动态逆序对

给定一个长度为 $n$ 的排列，$1\sim n$ 所有数字都出现一次

如果，前面的数 $>$ 后面的数，那么这两个数就组成一个逆序对

给定一个长度为 $m$ 的数组，表示依次删除的数字

打印每次删除数字前，排列中一共有多少逆序对，一共 $m$ 条打印

$1\le n\le {10}^5$

$1\le m\le 5\times {10}^4$

分析

代码实现

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

const int N = 100010, M = 50010;
struct Node {
    // v   : 值
    // idx : 下标
    // f   : 增加还是减少
    // q   : 问题编号
    int v, idx, f, q;
} e[N + M];
int c[N];
int n, m, tot, num[N], pos[N], del[M];
long long ans[N];

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

void add(int x, int y) {
    for (int i = x; i <= n; i += lowbit(i)) c[i] += y;
}

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

bool cmp(const Node& x, const Node& y) {
    return x.idx < y.idx;
}

void cdq(int l, int r) {
    if (l == r) return ;

    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);

    // 从左到右统计
    int p1 = l - 1, p2 = mid + 1;
    for (; p2 <= r; p2++) {
        while (p1 + 1 <= mid && e[p1 + 1].idx < e[p2].idx) {
            p1 ++;
            add(e[p1].v, e[p1].f);
        }
        ans[e[p2].q] += e[p2].f * (query(n) - query(e[p2].v));
    }

    for (int i = l; i <= p1; i++) add(e[i].v, -e[i].f);

    // 从右往左统计
    p1 = mid + 1, p2 = r;
    for (; p2 > mid; p2--) {
        while (p1 - 1 >= l && e[p1 - 1].idx > e[p2].idx) {
            p1 --;
            add(e[p1].v, e[p1].f);
        }
        ans[e[p2].q] += e[p2].f * query(e[p2].v - 1);
    }

    for (int i = mid; i >= p1; i--) add(e[i].v, -e[i].f);

    sort(e + l, e + r + 1, cmp);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
        pos[num[i]] = i;
    }
    for (int i = 1; i <= m; i++) cin >> del[i];

    for (int i = 1; i <= n; i++) {
        e[++tot] = {num[i], i, 1, 0};
    }
    for (int i = 1; i <= m; i++) {
        e[++tot] = {del[i], pos[del[i]], -1, i};
    }

    cdq(1, tot);

    for (int i = 1; i < m; i++) ans[i] += ans[i - 1];
    for (int i = 0; i < m; i++) cout << ans[i] << endl;

    return 0;
}

二维空间计数类（二维偏序）

洛谷 P2163. 园丁的烦恼

有 $n$ 棵树，每棵树给定位置坐标 $(x,y)$，接下来有 $m$ 条查询，格式如下

查询 a b c d: 打印左上角 $(a,b)$、右下角 $(c,d)$ 的区域里有几棵树

$0\le n\le 5\times {10}^5$

$1\le m\le 5\times {10}^5$

$0\le \mathrm{坐}\mathrm{标}\mathrm{值}\le {10}^7$

分析

树状数组实现

代码实现

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

const int N = 500010;
struct Node {
    int ty, x, y, v, q;
} e[5 * N], t[5 * N];
int n, m, tot, ans[5 * N];

bool cmp(const Node& l, const Node& r) {
    if (l.x != r.x) return l.x < r.x;
    return l.ty < r.ty;
}

void cdq(int l, int r) {
    if (l == r) return ;

    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);

    int p1 = l - 1, p2 = mid + 1, cnt = 0;
    for (; p2 <= r; p2++) {
        while (p1 + 1 <= mid && e[p1 + 1].y <= e[p2].y) {
            p1++;
            if (e[p1].ty == 1) cnt++;
        }

        if (e[p2].ty == 2) {
            ans[e[p2].q] += cnt * e[p2].v;
        }
    }

    p1 = l, p2 = mid + 1;
    int k = 1;
    while (p1 <= mid && p2 <= r) {
        t[k++] = e[p1].y < e[p2].y ? e[p1++] : e[p2++];
    }
    while (p1 <= mid) {
        t[k++] = e[p1++];
    }
    while (p2 <= r) {
        t[k++] = e[p2++];
    }
    for (int i = l, k = 1; i <= r; i++, k++) {
        e[i] = t[k];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x, y; cin >> x >> y;
        e[++tot] = {1, x, y};
    }
    for (int i = 1; i <= m; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        e[++tot] = {2, a - 1, b - 1, 1, i};
        e[++tot] = {2, c, d, 1, i};
        e[++tot] = {2, a - 1, d, -1, i};
        e[++tot] = {2, c, b - 1, -1, i};
    }

    sort(e + 1, e + 1 + tot, cmp);

    cdq(1, tot);

    for (int i = 1; i <= m; i++) {
        cout << ans[i] << endl;
    }

    return 0;
}

洛谷 P3755. 老 C 的任务

有 $n$ 个基站，每个基站给定 $x$、$y$、$v$，表示基站在 $(x,y)$ 位置，功率为 $v$

接下来有 $m$ 条查询，每条查询格式如下

查询 a b c d: 打印左上角 $(a,b)$、右下角 $(c,d)$ 的区域里基站的功率和

$1\le n,m\le {10}^5$

其余数值都在 int 类型的范围

分析

代码实现

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

const int N = 100010;
struct Node {
    int ty, x, y, v, q;
} e[5 * N], t[5 * N];
int n, m, tot;
long long ans[5 * N];

bool cmp(const Node& l, const Node& r) {
    if (l.x != r.x) return l.x < r.x;
    return l.ty < r.ty;
}

void cdq(int l, int r) {
    if (l == r) return ;

    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);

    int p1 = l - 1, p2 = mid + 1;
    long long cnt = 0;
    for (; p2 <= r; p2++) {
        while (p1 + 1 <= mid && e[p1 + 1].y <= e[p2].y) {
            p1++;
            if (e[p1].ty == 1) cnt += e[p1].v;
        }

        if (e[p2].ty == 2) {
            ans[e[p2].q] += cnt * e[p2].v;
        }
    }

    p1 = l, p2 = mid + 1;
    int k = 1;
    while (p1 <= mid && p2 <= r) {
        t[k++] = e[p1].y < e[p2].y ? e[p1++] : e[p2++];
    }
    while (p1 <= mid) {
        t[k++] = e[p1++];
    }
    while (p2 <= r) {
        t[k++] = e[p2++];
    }
    for (int i = l, k = 1; i <= r; i++, k++) {
        e[i] = t[k];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x, y, z; cin >> x >> y >> z;
        e[++tot] = {1, x, y, z};
    }
    for (int i = 1; i <= m; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        e[++tot] = {2, a - 1, b - 1, 1, i};
        e[++tot] = {2, c, d, 1, i};
        e[++tot] = {2, a - 1, d, -1, i};
        e[++tot] = {2, c, b - 1, -1, i};
    }

    sort(e + 1, e + 1 + tot, cmp);

    cdq(1, tot);

    for (int i = 1; i <= m; i++) {
        cout << ans[i] << endl;
    }

    return 0;
}

洛谷 P4390. 摩基亚

给定数字 $w$，表示一个 $w\times w$ 的正方形区域，所有位置都在其中

接下来有 $m$ 条操作，每种操作是如下两种类型中的一种：

1. 操作 1 x y v: 坐标 $(x,y)$ 位置增加了 $v$ 个人
2. 操作 2 a b c d: 打印左上角 $(a,b)$、右下角 $(c,d)$ 区域里的人数

$1\le w\le 2\times {10}^6$

$1\le m\le 2\times {10}^5$

$0\le v\le {10}^4$

分析

代码实现

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

const int N = 2000010, M = 10010;

struct Node {
    int ty, x, y, v, q;
} e[N];

int c[N];
int n, m, w, tot, ans[M];

bool cmp(const Node& l, const Node& r) {
    if (l.x != r.x) return l.x < r.x;
    return l.q < r.q;
}

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

void add(int x, int y) {
    for (int i = x; i <= w; i += lowbit(i)) c[i] += y;
}

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

void cdq(int l, int r) {
    if (l == r) return ;

    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);

    int p1 = l - 1, p2 = mid + 1;
    for (; p2 <= r; p2++) {
        while (p1 + 1 <= mid && e[p1 + 1].x <= e[p2].x) {
            p1++;
            if (e[p1].ty == 1) {
                add(e[p1].y, e[p1].v);
            }
        }
        if (e[p2].ty == 2) {
            ans[e[p2].q] += e[p2].v * query(e[p2].y);
        }
    }

    for (int i = l; i <= p1; i++) {
        if (e[i].ty == 1) {
            add(e[i].y, -e[i].v);
        }
    }

    sort(e + l, e + r + 1, cmp);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int op; cin >> op;
    cin >> w;
    w++;

    while (cin >> op) {
        if (op == 1) {
            int x, y, a; cin >> x >> y >> a;
            x++, y++;
            e[++tot] = {1, x, y, a};
        } else if (op == 2) {
            int a, b, c, d; cin >> a >> b >> c >> d;
            a++, b++, c++, d++;

            ++m;
            e[++tot] = {2, a - 1, b - 1, 1, m};
            e[++tot] = {2, c, d, 1, m};
            e[++tot] = {2, a - 1, d, -1, m};
            e[++tot] = {2, c, b - 1, -1, m};
        } else if (op == 3) {
            break;
        }
    }

    cdq(1, tot);

    for (int i = 1; i <= m; i++) cout << ans[i] << endl;

    return 0;
}

洛谷 P4169. 天使玩偶

规定 $(x_1,y_1)$ 和 $(x_2,y_2)$ 之间的距离 $=|x_1-x_2|+|y_1-y_2|$

一开始先给定 $n$ 个点的位置，接下来有 $m$ 条操作，每种操作是如下两种类型中的一种

1. 操作 1 x y: 在 $(x,y)$ 位置添加一个点
2. 操作 2 x y : 打印已经添加的所有点中，到 $(x,y)$ 位置最短距离的点是多远

$1\le n,m\le 3\times {10}^5$

$0\le x,y\le {10}^6$

分析

代码实现