56 · 分治与 CDQ 思想

上一节（回顾九）末尾给过一段十几行的归并排序求逆序对，说好“下一节再用到”，就是这里。那段代码看着像个小技巧，其实是分治的原型：把区间砍成两半，答案 = 左半 + 右半 + 跨中点的那一部分。前两项递归算，第三项在合并时顺手算完——分治的全部内容就是这个。

动手前先回答三个问题，答不出就别写：① 怎么切（两半规模尽量相等）；② 递归结束后两半各处于什么状态（归并排序：各自升序）；③ 合并时怎么在 O(n) 或 O(n log n) 内把跨中点的贡献算完。第 ③ 问是分治的全部难点，前两问是套路。

为什么合并时只管跨中点的对：若 i、j 同在某半内部，这一对在递归到那一层时已经数过；若 i、j 被中点分开，它只可能在这一层被数到——更外层的合并只统计跨它自己中点的对，根本不会碰到它。这就是不重不漏的来源。

先看两块骨架：分治函数怎么写、合并的双指针怎么写。这两块立住了，三维偏序只是在合并里塞一棵树状数组。

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

void solve(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    cout << "[" << l << "," << r << "]  mid = " << mid << "\n";
    solve(l, mid);          // 左半
    solve(mid + 1, r);      // 右半
}

int main() {
    solve(1, 8);            // 先看清“切”的形状，再往里加合并
    return 0;
}

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

int a[9] = {0, 1, 4, 7, 2, 5, 8, 9, 9};   // a[1..3] 与 a[4..8] 各自升序
int tmp[9];

int main() {
    int i = 1, j = 4, k = 1;
    while (i <= 3 && j <= 8) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= 3) tmp[k++] = a[i++];      // 左段剩余
    while (j <= 8) tmp[k++] = a[j++];      // 右段剩余
    for (int p = 1; p <= 8; ++p) cout << tmp[p] << " ";
    cout << "\n";                          // 1 2 4 5 7 8 9 9
    return 0;
}

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

const int N = 500005;
int n, a[N], tmp[N];
long long ans;                 // 上限 n(n-1)/2 ≈ 1.25e11，int 装不下

void msort(int l, int r) {
    if (l >= r) return;                  // 长度 1，天然有序
    int mid = (l + r) >> 1;
    msort(l, mid);                       // 先让两半各自有序
    msort(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];           // 取左边：这一对不是逆序对
        } else {
            ans += mid - i + 1;          // a[i..mid] 全都 > a[j]，一次加一整段
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int p = l; p <= r; ++p) a[p] = tmp[p];   // 抄回，供上层合并使用
}

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

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    msort(1, n);
    cout << ans << "\n";
    return 0;
}

下面是正题。逆序对其实是二维偏序：数满足 i < j 且 a[i] > a[j] 的对，等价于“下标一维、值一维”。把下标换成属性 a、值换成属性 b，就是数 aᵢ ≤ aⱼ 且 bᵢ ≤ bⱼ 的对。再加第三维 c，就得到三维偏序：排序管一维，分治管一维，树状数组管一维。

先拆开 CDQ 里唯一的新语法：三元组结构体 + 去重。看上去是存储问题，其实是正确性问题。

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

struct Node {
    int a, b, c, cnt, id;
} q[10];

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;                 // 全相等返回 false，保证相同元素相邻
}

int main() {
    int raw[5][3] = {{1, 2, 3}, {1, 2, 3}, {2, 1, 1}, {1, 2, 3}, {2, 1, 1}};
    int n = 5, tot = 0;
    for (int i = 1; i <= n; ++i) {
        q[i].a = raw[i - 1][0];
        q[i].b = raw[i - 1][1];
        q[i].c = raw[i - 1][2];
    }
    sort(q + 1, q + n + 1, cmp);

    for (int i = 1; i <= n; ++i) {
        if (tot && !cmp(q[tot], q[i])) ++q[tot].cnt;      // 与上一组完全相同
        else { q[++tot] = q[i]; q[tot].cnt = 1; q[tot].id = tot; }
    }

    for (int i = 1; i <= tot; ++i)
        cout << q[i].a << " " << q[i].b << " " << q[i].c
             << "  cnt=" << q[i].cnt << "  id=" << q[i].id << "\n";
    // 1 2 3 cnt=3 id=1   /   2 1 1 cnt=2 id=2
    return 0;
}

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

const int N = 100005;          // 元素个数上限
const int M = 200005;          // 属性值上限：树状数组下标是 c，要开到 2e5
int n, k, tot;
int bit[M];                    // 树状数组，管第三维 c
int ans[N];                    // ans[id]：比第 id 组小的元素个数
int res[N];                    // res[d]：f(i) = d 的元素个数

struct Node {
    int a, b, c, cnt, id;
} q[N], tmp[N];

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;
}

int lowbit(int x) { return x & -x; }
void add(int i, int v) { for (; i <= k; i += lowbit(i)) bit[i] += v; }
int sum(int i) { int s = 0; for (; i > 0; i -= lowbit(i)) s += bit[i]; return s; }

void cdq(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    cdq(l, mid);                       // 先把两半内部的答案算完
    cdq(mid + 1, r);                   // 两个递归结束后，两半各自按 b 有序

    // 合并：按 b 归并，只统计“左半 → 右半”的贡献
    int i = l, j = mid + 1, t = l;
    while (i <= mid && j <= r) {
        if (q[i].b <= q[j].b) {            // 左半这个 b 更小，它可以贡献给后面所有右半元素
            add(q[i].c, q[i].cnt);         // 第三维交给树状数组
            tmp[t++] = q[i++];
        } else {
            ans[q[j].id] += sum(q[j].c);   // 树里的都满足 b 更小，再查 c <= 它的有几个
            tmp[t++] = q[j++];
        }
    }
    while (i <= mid) { add(q[i].c, q[i].cnt); tmp[t++] = q[i++]; }
    while (j <= r) { ans[q[j].id] += sum(q[j].c); tmp[t++] = q[j++]; }

    for (int p = l; p <= mid; ++p) add(q[p].c, -q[p].cnt);   // 撤销本层，别污染外层
    for (int p = l; p <= r; ++p) q[p] = tmp[p];              // 按 b 有序写回
}

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

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> q[i].a >> q[i].b >> q[i].c;
    sort(q + 1, q + n + 1, cmp);

    for (int i = 1; i <= n; ++i) {                 // 相同三元组合并成一组
        if (tot && !cmp(q[tot], q[i])) ++q[tot].cnt;
        else { q[++tot] = q[i]; q[tot].cnt = 1; q[tot].id = tot; }
    }

    cdq(1, tot);

    for (int i = 1; i <= tot; ++i)                 // 同组内另外 cnt-1 个也要算
        res[ans[q[i].id] + q[i].cnt - 1] += q[i].cnt;
    for (int d = 0; d < n; ++d) cout << res[d] << "\n";
    return 0;
}

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

const int N = 100005;
int n, k;
long long s[N], tmp[N], inv;          // s: 减掉 k 之后的前缀和

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

    int i = l, j = mid + 1, t = l;
    while (i <= mid && j <= r) {
        if (s[i] <= s[j]) tmp[t++] = s[i++];       // 相等不算逆序对
        else { inv += mid - i + 1; tmp[t++] = s[j++]; }
    }
    while (i <= mid) tmp[t++] = s[i++];
    while (j <= r) tmp[t++] = s[j++];
    for (int p = l; p <= r; ++p) s[p] = tmp[p];
}

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

    cin >> n >> k;
    s[0] = 0;                                  // 空前缀，别忘了它
    for (int i = 1; i <= n; ++i) {
        long long a;
        cin >> a;
        s[i] = s[i - 1] + (a - k);             // 把“平均值 ≥ k”化成“前缀和不降”
    }

    msort(0, n);                               // n+1 个数，下标 0..n
    long long tot = (long long)(n + 1) * n / 2;
    cout << tot - inv << "\n";
    return 0;
}