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

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

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

思路

基本转化

假设不考虑任何修改，这就是个经典的贪心。将序列 $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)$ 值减一。
• 对于一个车将大于其位置的 $f(x)$ 值加一。
• 对于一辆车从 $u$ 挪到 $v$ 且 $u < v$，将在 $[u, v]$ 间的 $f(x)$ 减一。反之同理。

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

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

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

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

• 如果一个区间的 $\min \ge 0$：那么这个区间里所有的 $f(x)$ 都是非负的，此时 $\sum |f(x)| \cdot w = \sum f(x) \cdot w$。
• 如果一个区间的 $\max \le 0$：那么区间里所有 $f(x)$ 都是非正的，此时 $\sum |f(x)| \cdot w = -\sum f(x) \cdot w$。
• 如果 $\min < 0 < \max$：说明区间内正负号交替，我们才需要递归进入子节点处理。

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

1. 定义势能。我们定义节点 $v$ 的振幅 $A_v = \max_v - \min_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$）：

• 好性质：区间最大值等于最小值（区间所有数相等），或者区间最大值等于最小值加 $1$ 且开方后差值不变。此时开方操作可以直接等价为“区间减法”。
• 坏性质：数值差异大，暴力递归。

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

• 好性质：区间最大值严格小于 $x$。此时取模等于什么都没做，直接返回。
• 坏性质：最大值大于等于 $x$，暴力递归。