剑锋所指,心之所向。

cdq 分治是一种能将满足某些关系(通常是数值上的大于小于)的点聚集在一起的算法。

1 偏序问题

对于不同的偏序问题,主要是维数的区别。

1.0 归并排序

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

const int MAXN = 1e6 + 10;

int n, a[MAXN], p[MAXN];

#define mid ((l + r) >> 1)
void mergesort(int l, int r) {
    if (l == r) return ;
    mergesort(l, mid), mergesort(mid + 1, r);
    int h1 = l, h2 = mid + 1, cnt = l;
    while (h1 <= mid && h2 <= r) {
        if (a[h1] < a[h2]) p[cnt ++] = a[h1 ++];
        else p[cnt ++] = a[h2 ++];
    }
    while (h1 <= mid) p[cnt ++] = a[h1 ++];
    while (h2 <= r) p[cnt ++] = a[h2 ++];
    for (int i = l; i <= r; ++i) a[i] = p[i];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    mergesort(1, n);
    for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
    return 0;
}

归并排序的思想,即在回溯时,自底向上地合并。利用辅助数组 p[] 实现排序。

1.1 二维偏序

n 个元素,第 i 个元素有 a_{i}, b_{i } 两个属性,设 f(i) 表示满足 a_{j} \leq a_{i}b_{j} \leq b_{i}j \neq ij 的数量。

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


先将数组以 a_i 为第一关键字升序排序。

此时,对于数组中的某个位置 i,符合要求的 j 一定在 [1, i] 中。则只需要查询在一个前缀中小于某个值的数的个数。

对值域开一棵 BIT 即可。

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

const int MAXN = 1e6 + 10;

int n, f[MAXN];

struct node { int a, b, id; bool operator <(const node& b) { return a < b.a; } } arr[MAXN];

struct  BIT {
    int bit[MAXN];
    void init() { memset(bit, 0, sizeof bit); }
    void add(int x, int val) { for (; x <= n; x += (x & -x)) bit[x] += val; }
    int sum(int x) { int ret = 0; for (; x; x -= (x & -x)) ret += bit[x]; return ret; }
} bit;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &arr[i].a, &arr[i].b); arr[i].id = i;
    }
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; ++i) {
        f[bit.sum(arr[i].b)] ++;
        bit.add(arr[i].b, 1);
    }
    for (int i = 1; i < n; ++i) printf("%d ", f[i]);
    return 0;
}

1.2 三维偏序

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 \neq ij 的数量。

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


有了二维偏序的经验,可以发现,当只有最后一维非单调递增时,就可以用 BIT 进行维护,因为能产生贡献的一定在左边。则现在问题化为:如何在回溯时,使第一,二维有序。

联系到二维偏序对第一维的 sort,与归并排序在回溯时扫一遍的思想,有一个解决方案:

将整个序列以 a 为第一关键字排序。则对 i 有贡献的 j 一定在 i 左侧。在分治时我们只需要考虑左区间对右区间的贡献。

对于第二维,在分治回溯阶段,采取类似归并排序的方法,使得在左右子区间内部,从以 a 维关键字排序变成以 b 排序。

由于在回溯之前,整个区间是以 a 排序的。所以不论左区间怎么乱排,其所有的 a 都仍满足小于右区间的所有的 a

则计算左对右的贡献时,对左区间的值域开一个 BIT,对于右区间上的位置 i,只需在左区间找到最大的 b_j \leq b_i,在 BIT 中找到值小于 b_j 的个数即可。

注意到这个过程是可以和归并排序一起进行的。

时间复杂度:共 \log n 层,每层对 n 个点进行操作,单词操作为 BIT 的 \log n,故为 n \log^2 n

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

const int MAXN = 1e5 + 10, MAXK = 2e5 + 10;

int n, k, ans[MAXN];

struct BIT {
    int bit[MAXK];
    void add(int x, int val) { for (; x <= k; x += (x & -x)) bit[x] += val; }
    int sum(int x) { int ret = 0; for (; x; x -= (x & -x)) ret += bit[x]; return ret; }
} bit;

struct Triple {
    int a, b, c, cnt, ans;
    bool operator ==(const Triple& _) const {
        return a == _.a && b == _.b && c == _.c;
    }
} arr[MAXN], a[MAXN], tmp[MAXN];

bool cmpa(const Triple& x, const Triple& y) {
    return x.a < y.a || (x.a == y.a && x.b < y.b) || (x.a == y.a && x.b == y.b && x.c < y.c);
}

bool cmpb(const Triple& x, const Triple& y) {
    return x.b < y.b || (x.b == y.b && x.c < y.c) || (x.b == y.b && x.c == y.c && x.a < y.a);
}

#define mid ((l + r) >> 1)
void CDQ(int l, int r) {
    if (l == r) return ;
    CDQ(l, mid), CDQ(mid + 1, r);
    sort(a + l, a + mid + 1, cmpb), sort(a + mid + 1, a + r + 1, cmpb);
    int i = l, j = mid + 1, cur = l;
    for (; i <= mid && j <= r; ) {
        if (a[i].b <= a[j].b) bit.add(a[i].c, a[i].cnt), tmp[cur++] = q[i++];
        else a[j].ans += bit.sum(a[j].c), tmp[cur++] = q[j++];
    }
    for (; i <= mid; ) bit.add(a[i].c, a[i].cnt), tmp[cur++] = q[i++];
    for (; j <= r; ) a[j].ans += bit.sum(a[j].c), tmp[cur++] = q[j++];
    for (int k = l; k < i; ++k) bit.add(a[k].c, -a[k].cnt);
    for (int k = l; k <= r; ++k) q[k] = tmp[k];
}

int main() {
    int _n;
    scanf("%d %d", &_n, &k);
    for (int i = 1; i <= _n; ++i) {
        scanf("%d %d %d", &arr[i].a, &arr[i].b, &arr[i].c), arr[i].cnt = 1;
    }
    sort(arr + 1, arr + _n + 1, cmpa);
    for (int i = 1; i <= _n; ++i) {
        if (i == 1 || !(arr[i] == arr[i - 1])) a[++n] = arr[i];
        else a[n].cnt ++;
    }
    CDQ(1, n);   
    for (int i = 1; i <= n; ++i) ans[a[i].ans + a[i].cnt - 1] += a[i].cnt;
    for (int i = 0; i < _n; ++i) printf("%d\n", ans[i]);
    return 0;
}

1.4 四维偏序

待补(二维套二维就行?)

1.5 例题

[SHOI2007]园丁的烦恼

静态二维矩形和。


利用差分思想,将询问以 (a, b) 为左下角,(c, d) 为右上角的矩形内部和,拆成四个左下角均为 (0, 0) 的矩形的和差形式。之后就是三维偏序模板了。

时间复杂度 O(n \log^2 n)

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

const int MAXN = 3e6 + 10, MAXX = 1e7 + 10;

int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; ch < '0' || '9' < ch; ch = getchar()) if (ch == '-') f = -f;
    for (; '0' <= ch && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return f == -1 ? -x : x;
}

int n, m, ans[10000010];
struct node {
    int x, y, id, opt;
    bool operator <(const node& _) const { return (x < _.x) || (x == _.x && y < _.y) || (x == _.x && y == _.y && opt > _.opt); }
} q[MAXN << 1], tmp[MAXN << 1];

#define mid ((l + r) >> 1)
void CDQ(int l, int r) {
    if (l == r) return ;
    CDQ(l, mid), CDQ(mid + 1, r);
    int i = l, j = mid + 1, tot = 0, cur = l;
    for (;i <= mid && j <= r;) {
        if (q[i].y <= q[j].y) tot += q[i].opt, tmp[cur++] = q[i++];
        else ans[q[j].id] += tot, tmp[cur++] = q[j++];
    }
    for (;i <= mid;) tmp[cur++] = q[i++];
    for (;j <= r;) ans[q[j].id] += tot, tmp[cur++] = q[j++];
    for (int k = l; k <= r; ++k) q[k] = tmp[k];
}

int main() {
    n = read(), m = read();
    for (int i = 1, x, y; i <= n; ++i) {
        x = read(), y = read();
        q[i] = node{x, y, 0, 1};
    }
    int tmp_cnt = 0, tot_cnt = n;
    for (int i = 1, l1, r1, l2, r2; i <= m; ++i) {
        l1 = read(), r1 = read(), l2 = read(), r2 = read();
        q[++tot_cnt] = node{l2, r2, ++tmp_cnt, 0};
        q[++tot_cnt] = node{l2, r1 - 1, ++tmp_cnt, 0};
        q[++tot_cnt] = node{l1 - 1, r2, ++tmp_cnt, 0};
        q[++tot_cnt] = node{l1 - 1, r1 - 1, ++tmp_cnt, 0};
    }
    n = tot_cnt;
    sort(q + 1, q + n + 1);
    CDQ(1, n);
    for (int i = 1; i + 3 <= tmp_cnt; i += 4) {
        printf("%d\n", ans[i] - ans[i + 1] - ans[i + 2] + ans[i + 3]);
    }
    return 0;
}

[BOI2007]Mokia 摩基亚

动态加点,询问矩形和。


同上,将询问拆成四个二维偏序。

本质上是一个三维偏序问题,点 (x, y) 对询问 (a, b) 有贡献,当且仅当 t1 < t2, x < a, y < b,其中 t1 表示点 (x, y) 被加入的时间,t2 表示询问的时间。

特殊的是,在读入的时候,序列已经按 t 升序排序了,且任意点的 t 都不相同,所以就没必要再记录 t 这一维。

时间复杂度 O(n \log^2 n)

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

const int MAXN = 200000 + 10, MAXW = 2000000 + 10;

int w, n, q_cnt, tot_cnt, ans[MAXN];

struct Query {
    int x, y, id, opt;
    bool operator <(const Query& _) const {
        return (x < _.x) || (x == _.x && y < _.y) || (x == _.x && y == _.y && opt > _.opt);
    }
} q[MAXN];

struct BIT {
    int bit[MAXW];
    void add(int x, int val) { for (; x <= w + 3; x += (x & -x)) bit[x] += val; }
    int sum(int x) { int ret = 0; for (; x; x -= (x & -x)) ret += bit[x]; return ret; }
} bit;

#define mid ((l + r) >> 1)
void CDQ(int l, int r) {
    if (l == r) return ;
    CDQ(l, mid), CDQ(mid + 1, r);
    int i = l, j = mid + 1, cur = l;
    sort(q + l, q + mid + 1), sort(q + mid + 1, q + r + 1);
    for (; i <= mid && j <= r; ) {
        if (q[i].x <= q[j].x) bit.add(q[i++].y, q[i].opt);
        else ans[q[j++].id] += bit.sum(q[j].y);
    }
    for (; j <= r; ) ans[q[j++].id] += bit.sum(q[j].y);
    for (int k = l; k < i; ++k) bit.add(q[k].y, -q[k].opt);
}

int main() {
    int __;
    scanf("%d %d", &__, &w);
    for (int opt; scanf("%d", &opt) && opt != 3; ) {
        if (opt == 1) {
            int x, y, a;
            scanf("%d %d %d", &x, &y, &a);
            x++, y++;
            q[++tot_cnt] = Query{x, y, 0, a};
        } else {
            int l1, r1, l2, r2;
            scanf("%d %d %d %d", &l1, &r1, &l2, &r2); l1++, l2++, r1++, r2++;
            q[++tot_cnt] = Query{l2, r2, ++q_cnt, 0};
            q[++tot_cnt] = Query{l2, r1 - 1, ++q_cnt, 0};
            q[++tot_cnt] = Query{l1 - 1, r2, ++q_cnt, 0};
            q[++tot_cnt] = Query{l1 - 1, r1 - 1, ++q_cnt, 0};
        }
    }
    n = tot_cnt;
    CDQ(1, n);
    for (int i = 1; i + 3 <= q_cnt; i += 4) printf("%d\n", ans[i] - ans[i + 1] - ans[i + 2] + ans[i + 3]);
    return 0;
}

天使玩偶

动态加点,每次询问某点曼哈顿距离下最近点。


类似询问矩形和,将 \min(|x - x'| + |y - y'|) 拆成四个方向:

考虑询问点 (x, y) 的最近点。分四类讨论。

  1. (x, y) 左下角,即 x' < x, y' < y,原式变为 x + y - (x' + y'),维护 x' + y' 最大值。
  2. (x, y) 左上角,即 x' < x, y' > y,原式变为 x - y - (x' - y'),维护 x' - y' 最大值。
  3. (x, y) 右上角,即 x' > x, y' > y,原式变为 -x - y - (-x' - y'),维护 -x' - y' 最大值。
  4. (x, y) 右下角,即 x' > x, y' < y,原式变为 -x + y - (-x' + y'),维护 -x' + y' 最大值。

维护方式即,以 y 作为前/后缀,以对应最大值作为值塞入 BIT 即可。

时间复杂度 O(n \log^2 n)

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

const int MAXN = 1e6 + 10, MAXX = 1e6 + 10;
const int INF = 1e9;

int n, m, mxy, q_cnt, ans[MAXN];

void chkmax(int& a, int b) { if (a < b) a = b; }
void chkmin(int& a, int b) { if (a > b) a = b; }

int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; ch < '0' || '9' < ch; ch = getchar()) if (ch == '-') f = -f;
    for (; '0' <= ch && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return f == 1 ? x : -x;
}

struct node {
    int x, y, opt, id;
    bool operator <(const node& _) { return x < _.x || x == _.x && y < _.y || x == _.x; } //&& y == _.y && opt > _.opt; }
} q[MAXN], tmp[MAXN];

struct BIT {
    int bit[MAXX];
    void modify(int x, int val) { for (; x <= mxy; x += (x & -x)) chkmax(bit[x], val); }
    int query(int x) { int ret = -INF; for (; x; x -= (x & -x)) chkmax(ret, bit[x]); return ret; }
    void rmodify(int x, int val) { for (; x; x -= (x & -x)) chkmax(bit[x], val); }
    int rquery(int x) { int ret = -INF; for (; x <= mxy; x += (x & -x)) chkmax(ret, bit[x]); return ret; }
    void clear(int x) { for (; x <= mxy; x += (x & -x)) bit[x] = -INF; }
    void rclear(int x) { for (; x; x -= (x & -x)) bit[x] = -INF; }
    void clean() { for (int i = 0; i < MAXX; ++i) bit[i] = -INF; }
} bit[4];

void cdq(int l, int r) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int i = l, j = mid + 1, cur = l;
    for (; i <= mid && j <= r; ) {
        if (q[i].x <= q[j].x) {
            tmp[cur] = q[i]; cur++;
            if (!q[i].opt) { i++; continue; }
            bit[0].modify(q[i].y, q[i].x + q[i].y), bit[1].rmodify(q[i].y, q[i].x - q[i].y), i++;
        }
        else {
            tmp[cur] = q[j], cur++;
            chkmin(ans[q[j].id], abs(q[j].x + q[j].y - bit[0].query(q[j].y)));
            chkmin(ans[q[j].id], abs(q[j].x - q[j].y - bit[1].rquery(q[j].y)));
            j++;
        }
    }
    for (; i <= mid; ) tmp[cur++] = q[i++];
    for (; j <= r; ) {
        tmp[cur] = q[j]; cur++;
        chkmin(ans[q[j].id], abs(q[j].x + q[j].y - bit[0].query(q[j].y)));
        chkmin(ans[q[j].id], abs(q[j].x - q[j].y - bit[1].rquery(q[j].y)));
        j++;
    }
    for (int k = l; k < i; ++k) if (q[k].opt) {
        bit[0].clear(q[k].y), bit[1].rclear(q[k].y);
    }
    i = mid, j = r;
    for (; i >= l && j >= mid + 1; ) {
        if (q[i].x >= q[j].x) {
            if (!q[i].opt) { i--; continue; }
            bit[2].modify(q[i].y, -q[i].x + q[i].y), bit[3].rmodify(q[i].y, -q[i].x - q[i].y), i--;
        } 
        else {
            chkmin(ans[q[j].id], abs(-q[j].x + q[j].y - bit[2].query(q[j].y)));
            chkmin(ans[q[j].id], abs(-q[j].x - q[j].y - bit[3].rquery(q[j].y)));
            j--;
        }
    }
    for (; j >= mid + 1; ) {
        chkmin(ans[q[j].id], abs(-q[j].x + q[j].y - bit[2].query(q[j].y)));
        chkmin(ans[q[j].id], abs(-q[j].x - q[j].y - bit[3].rquery(q[j].y)));
        j--;
    }
    for (int k = mid; k > i; --k) if (q[k].opt) {
        bit[2].clear(q[k].y), bit[3].rclear(q[k].y);
    }
    for (int k = l; k <= r; ++k) q[k] = tmp[k];
}

int main() {
    n = read(), m = read();
    for (int i = 1, x, y; i <= n; ++i) {
        q[i].x = read(), q[i].y = read(), q[i].y++, q[i].opt = 1; mxy = max(mxy, q[i].y);
    }
    n += m;
    for (int i = n - m + 1, opt, x, y; i <= n; ++i) {
        opt = read(), x = read(), y = read();
        y++;
        if (opt == 1) q[i] = {x, y, 1, 0};
        else q[i] = {x, y, 0, ++q_cnt};
        mxy = max(mxy, q[i].y);
    }
    for (int i = 1; i <= n; ++i) ans[i] = INF;
    bit[0].clean(), bit[1].clean(), bit[2].clean(), bit[3].clean();
    cdq(1, n);
    for (int i = 1; i <= q_cnt; ++i) printf("%d\n", ans[i]);
    return 0;
}

[CQOI2011]动态逆序对

给出序列,按照某种顺序删除 m 个元素,求在每次删除之前,序列的逆序对数量。


考虑逆序对定义:i < j, a_i > a_j。在本题中,i, j 对序列的逆序对有贡献,当且仅当 i < j, a_i > a_j, t_i > t_j,其中 t_i 代表 i 被删除的时间。

则对于 i,统计所有 j > i, a_j < a_i, t_j > t_i,这些点就是当 i 被删除后,逆序对减少的数量。

不难看出这是一个三维偏序问题。

时间复杂度 O(n \log^2 n)

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

typedef long long ll;

const int MAXN = 1e5 + 10, MAXM = 5e4 + 10, MAXX = 1e5 + 10;

int n, m;
ll ans[MAXN], org;

struct BIT {
    ll bit[MAXX];
    void add(int x, ll val) { for (; x <= n; x += x & -x) bit[x] += val; }
    ll sum(int x) { ll ret = 0; for (; x; x -= x & -x) ret += bit[x]; return ret; }
    void radd(int x, ll val) { for (; x; x -= x & -x) bit[x] += val; }
    ll rsum(int x) { ll ret = 0; for (; x <= n; x += x & -x) ret += bit[x]; return ret; }
} bit[2];

int __tmp[MAXN];
struct node {
    ll val, pos, id;
    bool operator <(const node& _) const {
        return id > _.id || id == _.id && val < _.val || id == _.id && val == _.val && pos > _.pos;
    }
} q[MAXN], tmp[MAXN];

void cdq(int l, int r) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int i = l, j = mid + 1, cur = l;
    for (; i <= mid && j <= r; ) {
        if (q[i].val < q[j].val) bit[0].radd(q[i].pos, 1), tmp[cur++] = q[i], i++;
        else ans[q[j].id] += bit[0].rsum(q[j].pos), tmp[cur++] = q[j], j++;
    }
    for (; i <= mid; ) bit[0].radd(q[i].pos, 1), tmp[cur++] = q[i], i++;
    for (; j <= r; ) ans[q[j].id] += bit[0].rsum(q[j].pos), tmp[cur++] = q[j], j++;
    for (int k = l; k < i; ++k) bit[0].radd(q[k].pos, -1);
    i = mid, j = r;
    for (; i >= l && j >= mid + 1; ) {
        if (q[i].val > q[j].val) bit[1].add(q[i].pos, 1), i--;
        else ans[q[j].id] += bit[1].sum(q[j].pos), j--;
    }
    for (; j >= mid + 1; ) ans[q[j].id] += bit[1].sum(q[j].pos), j--;
    for (int k = mid; k > i; --k) bit[1].add(q[k].pos, -1);
    for (int k = l; k <= r; ++k) q[k] = tmp[k];
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        ll x;
        scanf("%lld", &x), q[i].val = x, q[i].pos = i, __tmp[x] = i, q[i].id = m + 1;
    }
    for (int i = 1; i <= m; ++i) {
        ll x;
        scanf("%lld", &x);
        q[__tmp[x]].id = i;
    }
    sort(q + 1, q + n + 1);
    cdq(1, n);
    for (int i = 1; i <= m + 1; ++i) org += ans[i];
    for (int i = 1; i <= m; ++i) {
        printf("%lld\n", org);
        org -= ans[i];
    }
    return 0;
}

CF1093E Intersection of Permutations

两个 1 \sim n 排列 a, b,涉及以下操作:

  1. 给出 l_a, r_a, l_b, r_b|S_a \cap S_b|,其中 S_a = \{a_i \mid i \in [l_a, r_a]\}, S_b = \{b_i \mid i \in [l_b, r_b]\}
  2. 给出 x, y,交换 b_x, b_y

对于 1 操作,考虑构建映射 p1(a_i) \rightarrow ip2(b_i) \rightarrow i。询问等价于 \sum p1(i) \in [l_a, r_a] \land p2(i) \in [l_b, r_b]。就是一个典型的矩阵求和。

考虑操作 2,在原坐标处加入一个权值为 -1 的点来消除原影响,并在新坐标加入点即可。

因此,cdq 分治的考法,经常在于如何插入询问。

时间复杂度 O(n \log^2 n)

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

typedef long long ll;

const int MAXN = 4e6 + 10;

int n, m, arr[2][MAXN], cod[2][MAXN], tot_cnt, q_cnt, ans[MAXN];

struct Query {
    int x, y, id, val, mul;
} q[MAXN], tmp[MAXN];

struct BIT {
    int bit[MAXN];
    void _add(int x, int val) { for (; x <= n + 5; x += x & -x) bit[x] += val; }
    int _query(int x) { int ret = 0; for (; x; x -= x & -x) ret += bit[x]; return ret; }
    void add(int x, int val) { _add(x + 1, val); }
    int query(int x) { return _query(x + 1); }
} bit;

void cdq(int l, int r) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int i = l, j = mid + 1, cur = l;
    for (; i <= mid && j <= r; ) {
        if (q[i].x <= q[j].x) bit.add(q[i].y, q[i].val), tmp[cur++] = q[i++];
        else ans[q[j].id] += bit.query(q[j].y) * q[j].mul, tmp[cur++] = q[j++];
    }
    for (; i <= mid; ) bit.add(q[i].y, q[i].val), tmp[cur++] = q[i++];
    for (; j <= r; ) ans[q[j].id] += bit.query(q[j].y) * q[j].mul, tmp[cur++] = q[j++];
    for (int k = l; k < i; ++k) bit.add(q[k].y, -q[k].val);
    for (int k = l; k <= r; ++k) q[k] = tmp[k];
}

int main() {
    scanf("%d %d", &n, &m);
    for (int _ = 0; _ <= 1; ++_) for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[_][i]);
        cod[_][arr[_][i]] = i;
    }
    for (int i = 1; i <= n; ++i) {
        q[++tot_cnt] = {cod[0][i], cod[1][i], 0, 1, 0};
    }
    for (int i = 1, opt; i <= m; ++i) {
        scanf("%d", &opt);
        if (opt == 1) {
            int l1, r1, l2, r2;
            scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
            q[++tot_cnt] = {r1, r2, ++q_cnt, 0, 1};
            q[++tot_cnt] = {l1 - 1, r2, q_cnt, 0, -1};
            q[++tot_cnt] = {r1, l2 - 1, q_cnt, 0, -1};
            q[++tot_cnt] = {l1 - 1, l2 - 1, q_cnt, 0, 1};
        } else {
            int x, y;
            scanf("%d %d", &x, &y);
            q[++tot_cnt] = {cod[0][arr[1][x]], cod[1][arr[1][x]], 0, -1, 0};
            q[++tot_cnt] = {cod[0][arr[1][y]], cod[1][arr[1][y]], 0, -1, 0};
            swap(arr[1][x], arr[1][y]);
            cod[1][arr[1][y]] = y, cod[1][arr[1][x]] = x;
            q[++tot_cnt] = {cod[0][arr[1][x]], cod[1][arr[1][x]], 0, 1, 0};
            q[++tot_cnt] = {cod[0][arr[1][y]], cod[1][arr[1][y]], 0, 1, 0};
        }
    }
    cdq(1, tot_cnt);
    for (int i = 1; i <= q_cnt; ++i) printf("%d\n", ans[i]);
    return 0;
}

CF848C Goodbye Souvenir

定义 f(i, l, r)\ (i \in [l, r]) 为,a_i[l, r] 内最后一次出现的位置,减去第一次出现的位置。

给出序列,涉及以下操作:

  1. 给出 p, x,将 a_p 改为 x
  2. 给出 l, r,求 \displaystyle \sum_{i \in [l, r]} f(i, l, r)

a_i 的上一次出现为 pre_i,下一次为 nxt_i

考虑对询问 l, r 有贡献的 i 满足什么条件。i \in [l, r] \land pre_i \in[l, r] 是其必要条件。

关于形如这种值的 trick:将元素的权值赋为 i - pre_i,询问一个区间的和就是区间的值。

同理,我们以 i 为横座标,pre_i 为纵坐标,i - pre_i 为权值。对于询问,求处以 (l_a, l_b) 为左下角,(r_a, r_b) 为右上角的矩形内所有点的权值和即可。

考虑维护 2 操作。2 操作将会变动一系列的 prenxt。我们对每个值的开一个 set,维护其出现的位置,二分出变动的 prenxt。值得注意的是,对于每个被更改的 pre,都要将其删除再插入。具体见代码。

时间复杂度 O(n \log^2 n)

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

typedef long long ll;

const int MAXN = 1000000 + 10;

int n, m, arr[MAXN], pre[MAXN], nxt[MAXN], lst[MAXN];
ll ans[MAXN];

int tot_cnt, q_cnt;
struct node {
    int x, y, val, id, mul;
} q[MAXN], tmp[MAXN];

void del(int x) { q[++tot_cnt] = {x, pre[x], pre[x] - x, 0, 0}; }
void add(int x) { q[++tot_cnt] = {x, pre[x], x - pre[x], 0, 0}; }

set<int> col[MAXN];

struct BIT {
    ll bit[MAXN];
    void _add(int x, int val) { for (; x <= n + 5; x += x & -x) bit[x] += val; }
    ll _query(int x) { ll ret = 0; for (; x; x -= x & -x) ret += bit[x]; return ret; } 
    void add(int x, int val) { _add(x + 2, val); }
    ll query(int x) { return _query(x + 2); } 
} bit;

void cdq(int l, int r) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int i = l, j = mid + 1, cur = l;
    for (; i <= mid && j <= r; ) {
        if (q[i].x <= q[j].x) bit.add(q[i].y, q[i].val), tmp[cur++] = q[i++];
        else ans[q[j].id] += bit.query(q[j].y) * q[j].mul, tmp[cur++] = q[j++];
    }
    for (; i <= mid; ) bit.add(q[i].y, q[i].val), tmp[cur++] = q[i++];
    for (; j <= r; ) ans[q[j].id] += bit.query(q[j].y) * q[j].mul, tmp[cur++] = q[j++];
    for (int k = l; k < i; ++k) bit.add(q[k].y, -q[k].val);
    for (int k = l; k <= r; ++k) q[k] = tmp[k];
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= n; ++i) col[i].insert(0), col[i].insert(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]), pre[i] = lst[arr[i]], lst[arr[i]] = i, col[arr[i]].insert(i);
    }
    for (int i = 1; i <= n; ++i) lst[i] = n + 1;
    for (int i = n; i >= 1; --i) nxt[i] = lst[arr[i]], lst[arr[i]] = i;
    for (int i = 1; i <= n; ++i) add(i);
    for (int _ = 1, opt; _ <= m; ++_) {
        scanf("%d", &opt);
        if (opt == 1) {
            int p, x;
            scanf("%d %d", &p, &x);
            if (x == arr[p]) continue;
            del(p);
            int _nn = nxt[p], _pp = pre[p];
            if (_nn != n + 1) del(_nn), pre[_nn] = _pp, add(_nn);
            if (_pp != 0) nxt[_pp] = _nn;
            _pp = *--col[x].lower_bound(p);
            _nn = *col[x].lower_bound(p);
            if (_nn != n + 1) del(_nn), pre[_nn] = p, add(_nn);
            if (_pp != 0) nxt[_pp] = p;
            col[arr[p]].erase(p), col[x].insert(p), arr[p] = x, pre[p] = _pp, nxt[p] = _nn;
            add(p);
        } else {
            int l, r;
            scanf("%d %d", &l, &r);
            q[++tot_cnt] = {r, r, 0, ++q_cnt, 1};
            q[++tot_cnt] = {l - 1, l - 1, 0, q_cnt, 1};
            q[++tot_cnt] = {l - 1, r, 0, q_cnt, -1};
            q[++tot_cnt] = {r, l - 1, 0, q_cnt, -1};
        }
    }
    cdq(1, tot_cnt);
    for (int i = 1; i <= q_cnt; ++i) printf("%lld\n", ans[i]);
    return 0;
}

CF1045G AI robots

n 个机器人,每个机器人有其坐标 x_i,视野 r_i,智商 q_i。机器人 i, j 能互相看到,当且仅当 x_i \in [x_j - r_j, x_j + r_j] \land x_j \in [x_i - r_i, x_i + r_i] \land |q_i - q_j| \leq k。求有多少对机器人能互相看见。


非常棘手的是,互相看到是关于 i, j 的,没办法直接 cdq。考虑如何转化为只与 i 相关。

使机器人按 r 降序排序,这样对于 j < i,如果 i 能看见 j,易知 j 必定可以看见 i。此时,对于 i,统计 j < i, x_j \in [x_i - r_i, x_i + r_i], q_j \in [q_i - k, q_i + k] 的点即可。

时间复杂度 O(n \log^2 n)

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

typedef long long ll;

const int MAXN = 3e6 + 10;

int n, k, cod[MAXN], cpy[MAXN], mn;
ll ans;

struct node {
    int x, l, r, len, q;
    bool operator <(const node& _) const {
        return len > _.len;
    }
} arr[MAXN];

int tot_cnt;
struct Query {
    int y, x, val, mul;
} q[MAXN], tmp[MAXN];

struct BIT {
    ll bit[MAXN];
    void _add(int x, int val) { for (; x < MAXN; x += x & -x) bit[x] += val; }
    ll _query(int x) { ll ret = 0; for (; x; x -= x & -x) ret += bit[x]; return ret; }
    void add(int x, int val) { _add(x + -mn + 1, val); }
    ll query(int x) { return _query(x + -mn + 1); }
} bit;

void cdq(int l, int r) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int i = l, j = mid + 1, cur = l;
    for (; i <= mid && j <= r; ) {
        if (q[i].x <= q[j].x) bit.add(q[i].y, q[i].val), tmp[cur++] = q[i++];
        else ans += bit.query(q[j].y) * q[j].mul, tmp[cur++] = q[j++];
    }
    for (; i <= mid; ) bit.add(q[i].y, q[i].val), tmp[cur++] = q[i++];
    for (; j <= r; ) ans += bit.query(q[j].y) * q[j].mul, tmp[cur++] = q[j++];
    for (int k = l; k < i; ++k) bit.add(q[k].y, -q[k].val);
    for (int k = l; k <= r; ++k) q[k] = tmp[k];
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d %d %d", &arr[i].x, &arr[i].len, &arr[i].q), cod[i] = cpy[i] = arr[i].x;
    sort(cod + 1, cod + n + 1); int _n = unique(cod + 1, cod + n + 1) - cod - 1;
    for (int i = 1; i <= n; ++i) {
        arr[i].l = lower_bound(cod + 1, cod + _n + 1, arr[i].x - arr[i].len) - cod;
        arr[i].r = upper_bound(cod + 1, cod + _n + 1, arr[i].x + arr[i].len) - cod - 1;
        arr[i].x = lower_bound(cod + 1, cod + _n + 1, arr[i].x) - cod;
    }
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; ++i) {
        mn = min(mn, arr[i].q - k - 1);
        q[++tot_cnt] = {arr[i].r, arr[i].q + k, 0, 1};
        q[++tot_cnt] = {arr[i].l - 1, arr[i].q + k, 0, -1};
        q[++tot_cnt] = {arr[i].r, arr[i].q - k - 1, 0, -1};
        q[++tot_cnt] = {arr[i].l - 1, arr[i].q - k - 1, 0, 1};
        q[++tot_cnt] = {arr[i].x, arr[i].q, 1, 0};
    }
    cdq(1, tot_cnt);
    printf("%lld\n", ans);
    return 0;
}

优化 DP

将某一类点通过排序,归并放在一起

例题:[SDOI2011]拦截导弹

求二维最长不上升子序列,与每个点被选入最长不上升子序列的概率。

首先考虑求长度。

f(i) = \max f(j) + 1 \ (j < i, a_j \geq a_i, b_j \geq b_i)

有了偏序问题的经验,我们可以通过一些操作,将满足要求的点放在一起,并通过 BIT 这一数据结构维护区间操作。

具体而言,在 BIT 上询问该区间的 max,并更新 f(i)

考虑求方案数,i 在 LDS 上的冲要条件为 l = f1(i) + f2(i) - 1,其中 l 代表 LDS 长度,f1 代表以其为结尾的 LDS 长度,f2 为以其为开头的 LDS 长度。

同理,方案数 g(i) = g1(i) \times g2(i),其中 g1 代表以其为结尾的 LDS 的方案数。

g1(i) = \sum g1(j) \ (f1(j) = f1(i) - 1),同理可得 g2。这些也是可以通过 BIT 维护的。

代码咕了。

斜率优化

例题:NOI 2007 Cash 货币优化

cdq 的论文 中所提到的 cdq 分治的第一个用法便是来处理该类斜率优化的问题。

该题的式子:

f_i = b_i * (g_j * r_j * \dfrac{a_i}{b_i} + g_j)

其中 g_i = \dfrac{f_i}{r_i * a_i + b_i}

可以得到:

x_i = g_i * r_i, y_i = g_i, k_i = -\dfrac{a_i}{b_i}

可以发现,无论是一个点的横坐标,还是在求该点 f 值所需要的 k 值,都不是单调递增或递减的。这意味着传统的单调队列或 wqs 二分都无法解决这个问题。

考察单调队列的过程:所有的点的 x 坐标递增,这样便于维护凸包;所有的点 k 具有单调性,这样可以使得单调队列直接去尾而不用二分。

而恰好 cdq 分治可以通过归并,排序等方法使得左,右子区间满足某些性质。

对应到这个问题:我们通过一些手段,使得左区间的点的 x 递增,右区间的 k 递减,从而可以用通过单调队列,来让左区间的点更新右区间的点。

一个小问题:递归左右与左更新右的顺序是怎样的?

考虑递归树,cdq 分治的递归树是对询问的一棵满二叉树。不同的顺序对应的是遍历的方式。

例如,先递归完子区间再更新,是后序遍历。递归左区间,更新,递归右区间是中序遍历。

在之前的点对问题中,我们一直采用的是后序遍历。但此时,因为 DP 的特殊性质,后序遍历是错误的。

具体而言,由于后序遍历是最后才更新左区间对右区间的贡献,所以在递归右区间时,其内部并没有被完全更新完,并不是最终的状态,用非最终状态来更新自然就是错误的了。不过这也仅限 DP 问题,在计数问题中这是不存在的。

而中序遍历是在递归右区间之前就计算了左区间对右区间的贡献,递归右区间时,某些点已经是最终状态了。故其正确性有保障。

那么,这就是一个 O(n \log n) 的离线算法了。

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

typedef long long ll;
typedef long double db;

const int MAXN = 1e5 + 10;
const db eps = 1e-8;

int n, S;
db ans[MAXN], g[MAXN], a[MAXN], b[MAXN], rate[MAXN];

struct node {
    db x, y, k; int id;
    bool operator <(const node& _) const {
        return k > _.k + eps;
    }
} cdq[MAXN], tmp[MAXN], que[MAXN];
db slope(const node& a, const node& b) {
    if (fabs(a.x - b.x) < eps) return a.y > b.y ? 1e18 : -1e18;
    return (a.y - b.y) / (a.x - b.x);
}

void cdq_dvd_cnq(int l, int r) {
    if (l == r) {
        int i = cdq[l].id;
        ans[i] = max(ans[i], ans[i - 1]);
        g[i] = ans[i] / (rate[i] * a[i] + b[i]);
        cdq[l].x = g[i] * rate[i], cdq[l].y = g[i];
        return ;
    }
    int mid = (l + r) >> 1, i = l, j = mid + 1;
    for (int k = l; k <= r; ++k) {
        if (cdq[k].id <= mid) tmp[i++] = cdq[k];
        else tmp[j++] = cdq[k];
    }
    for (int k = l; k <= r; ++k) cdq[k] = tmp[k];
    cdq_dvd_cnq(l, mid);
    int hd = 1, tl = 0;
    for (int k = l; k <= mid; ++k) {
        for (; hd < tl && slope(que[tl], que[tl - 1]) < slope(cdq[k], que[tl]) + eps; ) tl--;
        que[++tl] = cdq[k];
    }
    for (int k = mid + 1; k <= r; ++k) {
        for (; hd < tl && slope(que[hd + 1], que[hd]) + eps >= cdq[k].k; ) hd++;
        int j = que[hd].id, i = cdq[k].id;
        ans[i] = max(ans[i], g[j] * rate[j] * a[i] + g[j] * b[i]);
    }
    cdq_dvd_cnq(mid + 1, r);
    i = l, j = mid + 1; int cur = l;
    for (; i <= mid && j <= r; ) {
        if (cdq[i].x < cdq[j].x + eps) tmp[cur++] = cdq[i++];
        else tmp[cur++] = cdq[j++];
    }
    for (; i <= mid; ) tmp[cur++] = cdq[i++];
    for (; j <= r; ) tmp[cur++] = cdq[j++];
    for (int k = l; k <= r; ++k) cdq[k] = tmp[k];
}

int main() {
    scanf("%d %d", &n, &S);
    for (int i = 1; i <= n; ++i) {
        scanf("%Lf %Lf %Lf", &a[i], &b[i], &rate[i]);
        cdq[i].id = i, cdq[i].k = -a[i] / b[i];
    }
    ans[0] = S;
    sort(cdq + 1, cdq + n + 1);
    cdq_dvd_cnq(1, n);
    printf("%.5Lf\n", ans[n]);
    return 0;
}

总结

cdq 分治的本质,是将满足某些关系的点聚集在一起。

不论是点对问题(某些关系:a_j < a_i, b_j < b_i \cdots),还是二维 LIS(a_j > a_i, b_j > b_i),还是维护斜率优化(k_i > k_j, x_i < x_jcdq 分治都是通过归并,排序等方法把这些满足性质的点放在了一起,从而优化复杂度(因为通常来说 n 次单点操作的复杂度是小于做 1 次长度为 n 的区间操作)。所以我们可以发现,cdq 分治的考点,是在于发现这些性质,并联系到 cdq 分治,从而解决问题。

OI-分治-cdq分治

题解 BZOJ 2238 Mst | 树上倍增
上一篇 «
CWOI 6-6 提高练习赛 2 测试题解与总结
» 下一篇