题解：P3992 [BJOI2017] 开车

· · 题解

竟然没有线段树做法，我来提供一个。用时在平均以上。

基本转化和大家类似，可以重点看线段树部分。

个人感觉是道势能线段树好题，可以让你的相关经验大幅提高。

思路

基本转化

假设不考虑任何修改，这就是个经典的贪心。将序列 a、b 分别从小到大排序，然后两两对应计算距离。证明方法不再赘述。

但是点对点的匹配关系随着修改极易破裂，这个视角的做法就行不通了。因为每次修改维护十分复杂代价也很大。

想想一个车去到加油站的贡献本质，就是经过了一段路的长度。

于是可以考虑用贡献法，计算每段路被经过的次数。

离散化后，设 C(x) 表示坐标 < x 的车辆总数，D(x) 表示坐标 < x 的加油站总数。我们定义它们的前缀差值函数 f(x) = C(x) - D(x)。

那么第 x - 1 段路被通过的次数就是 f(x) 的绝对值。

举个例子：想象一下，在位置 x 和 x - 1 之间画一条竖线，把整个数轴砍成左右两半，如果 f(x) 为 3 就意味着这条竖线的左边车比加油站多 3。那么这多出来的车想要找到加油站只能去这条线的右边，从而这段路就会被经过 3 次。负数的情况同理。

那么我们就要求 \sum_{x = 1}^{m} |f(x)|，m 为路的段数。

线段树实现

先看看维护 f(x) 需要满足什么样的操作。

这不就是维护区间修改嘛，第一直觉绝对是线段树。

这时肯定有人要问，f(x) 有正有负，如何合并，直接合并不是乱套了？

这个时候我们可以回顾一下吉司机线段树的重要思想——直接处理好区间，暴力处理坏区间。想想模板（P6242【模板】线段树 3（区间最值操作、区间历史最值）），是不是大于次大值的取 \min 可以直接处理，否则就继续下去。

通常线段树很难直接处理 |f(x)|，但在这道题里，f(x) 的修改非常有规律（每次只 \pm 1）。我们可以利用线段树维护区间的最小值和最大值：

正确性证明（势能分析）如下。

  1. 定义势能。我们定义节点 v 的振幅 A_v = \max_v - \min_v。定义整个线段树系统的总势能为

    \Phi = \sum_{v \in \text{Tree}} A_v。

  2. 常规修改下势能增量。当我们执行一次区间修改时，线段树上的节点分为两类。

    • 完全被覆盖的节点：区间里的所有数同时 + 1 或 - 1。最大值和最小值同时平移，它们的振幅 A_v 绝对不发生变化。
    • 边界被切断的节点（未完全覆盖）：只有落在 L 和 R 边界上的 O(\log n) 个节点，其内部的一部分元素被修改了。每次 \pm 1 操作，最多让这些边界节点的振幅 A_v 增加 1。
    • 结论：每次操作，整个系统的总势能 \Phi 最多增加 O(\log n)。经过 Q 次操作，系统总势能的增加量被限制在 O(Q \log n)。

  3. 势能消耗。只有当区间正负交替（跨越零点）时。此时必然满足 \min_v < 0 < \max_v。因为我们处理的是整数，这意味着此时该节点的振幅 A_v \ge 2。其实，如果允许任意跨度的区间加减（比如一下加 100，一下减 100），这个算法是会被卡成 O(n \times Q) 导致 TLE 的。因为大跨度的加减法可以让一个区间在正负之间反复横跳，不停地无谓跨越零点，而振幅并不减小。但这题可行是因为这题的修改值永远是极小的 \pm 1。

  4. 总结。初始建树时，势能 \Phi_0 = O(N \log N)。Q 次操作，补充势能 \Delta \Phi = O(Q \log N)。均摊复杂度 O(n \log n + q \log n)。

代码

就是经典的线段树操作，小心循环变量与实体 ID 的混淆、离散化坐标的“点”与“段”的错位就行了。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int n, q;
int a[N], b[N];
pair<int, int> mdf[N];
vector<int> X;
int cnt; // 离散化去重后，坐标池中有效元素的个数
typedef long long ll;
struct Node {
    // f(x) = c(x) - d(x) 车减去油，相关参数维护的都是 f(x)
    int minv, maxv;
    ll sum, ans, len; // sum 实际情况，ans 取绝对值之后的情况
    int tag;
} tr[N << 2];

void push_up(int x) {
    auto &t = tr[x], &ls = tr[x << 1], &rs = tr[x << 1 | 1];
    t.maxv = max(ls.maxv, rs.maxv);
    t.minv = min(ls.minv, rs.minv);
    t.sum = ls.sum + rs.sum;
    t.ans = ls.ans + rs.ans;
    t.len = ls.len + rs.len;
}

void build(int x, int l, int r) {
    auto &t = tr[x]; // X 数组是 0 索引的
    if (l == r) {
        t.len = X[l] - X[l - 1];
        t.sum = t.ans = t.minv = t.maxv = t.tag = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    push_up(x);
}

void push_down(int x) {
    auto &t = tr[x], &ls = tr[x << 1], &rs = tr[x << 1 | 1];
    int val = t.tag;
    if (!t.tag) return;

    ls.maxv = ls.maxv + val;
    ls.minv = ls.minv + val;
    ls.sum += val * ls.len;
    ls.ans = abs(ls.sum);
    ls.tag += val;

    rs.maxv = rs.maxv + val;
    rs.minv = rs.minv + val;
    rs.sum += val * rs.len;
    rs.ans = abs(rs.sum);
    rs.tag += val;

    t.tag = 0;
    /*
    如果父节点能够成功打上 tag（即满足了不跨越 0 的条件），
    说明父节点所辖区间内的所有最值都不会跨越 0。
    既然父节点都是安全的，那么它的左右子节点绝对也是安全的。
    */
}

void modify(int x, int l, int r, int L, int R, int val) {
    if (L > R) return;
    auto &t = tr[x];
    if (L <= l and r <= R) {
        // 实际上，只要修改后的新区间满足全正或全负即可，
        // 不需要管原来是不是正负交替，我写的比较保守
        if ((l == r) or (t.minv >= 0 and t.minv + val >= 0) or (t.maxv <= 0 and t.maxv + val <= 0)) {
            t.maxv = t.maxv + val;
            t.minv = t.minv + val;
            t.sum += val * t.len;
            t.ans = abs(t.sum);
            t.tag += val;
            return;
        }
    }
    push_down(x);

    int mid = (l + r) >> 1;
    if (L <= mid) modify(x << 1, l, mid, L, R, val);
    if (R > mid) modify(x << 1 | 1, mid + 1, r, L, R, val);
    push_up(x);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        X.push_back(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        X.push_back(b[i]);
    }
    cin >> q;

    for (int i = 1; i <= q; i++) {
        cin >> mdf[i].first >> mdf[i].second;
        X.push_back(mdf[i].second);
    }

    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    cnt = X.size();
    // 节点 i 代表的是 [x(i-1), x(i))

    if (cnt > 1) build(1, 1, cnt - 1);

    for (int i = 1; i <= n; i++) {
        int p = lower_bound(X.begin(), X.end(), a[i]) - X.begin() + 1;
        modify(1, 1, cnt - 1, p, cnt - 1, 1);
    }
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(X.begin(), X.end(), b[i]) - X.begin() + 1;
        modify(1, 1, cnt - 1, p, cnt - 1, -1);
    }

    cout << tr[1].ans << "\n";
    for (int i = 1; i <= q; i++) {
        int id = mdf[i].first, x = mdf[i].second;
        int pu = lower_bound(X.begin(), X.end(), a[id]) - X.begin() + 1;
        int pv = lower_bound(X.begin(), X.end(), x) - X.begin() + 1;
        if (pu < pv) modify(1, 1, cnt - 1, pu, pv - 1, -1); // 最后一个节点容易出锅
        else if (pu > pv) modify(1, 1, cnt - 1, pv, pu - 1, 1);
        a[id] = x;
        cout << tr[1].ans << "\n";
    }
    return 0;
}

启示：这种思想如何扩展？

只要你能找到“好性质”和“坏性质”的分界线，这种思想可以扩展到无数非线性操作上。

区间开平方（a_i \gets \lfloor \sqrt{a_i} \rfloor）：

区间取模（a_i \gets a_i \bmod x）：