题目详细题解

一、题目核心分析

1. 关键定义

• 几乎必然相等：修改其中一个多重集至多一个元素后，两个多重集完全相等。
• 操作规则：对数组$a$的元素仅能执行减1操作，$b$数组固定不变，操作次数为$a_i$减少的总数值。
• 问题要求：对每个前缀长度$k$（$1 \leq k \leq n$），求使$a[1..k]$和$b[1..k]$的多重集几乎必然相等的最少操作次数。

2. 转化问题

设对于前缀$k$，$sum = \sum_{i=1}^k (a_i - b_i)$，表示将$a[1..k]$完全变成$b[1..k]$的总操作次数。 根据“几乎必然相等”的定义，我们可以保留一个元素不被压缩到$b_i$（即该元素的操作次数为$0$），或调整一个元素的取值，使得剩余元素的操作次数总和最小。 最优策略是：找到一个最大的区间$[l, r]$，使得该区间覆盖的“可节省操作次数”最大，最终答案为$sum - \text{max\_save}$（$\text{max\_save}$为最大可节省的操作次数）。

二、算法思路

1. 核心观察

每个元素$i$对应区间$[b_i, a_i]$，区间长度$a_i - b_i$是该元素的总操作次数。 将这些区间合并重叠/相邻的区间后，最大的合并区间长度即为$\text{max\_save}$（因为保留这个区间对应的元素不压缩，能节省最多操作次数）。

2. 算法步骤

1. 计算总操作次数：对每个前缀$i$，累加$sum = sum + (a_i - b_i)$。
2. 区间合并：用有序集合$\text{segs}$维护不相交的区间，插入当前元素的$[b_i, a_i]$并合并重叠区间。
3. 维护最大区间长度：记录合并后最大的区间长度$\text{best}$。
4. 计算答案：每个前缀的答案为$sum - best$（总操作次数减去最大可节省的操作次数）。

三、代码逐行解析

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速输入输出

    int T;  cin >> T;
    while (T--) {
        int n;  cin >> n;
        vector<int64> a(n), b(n);
        for (auto &x: a) cin >> x;
        for (auto &x: b) cin >> x;

        std::set<pair<int64,int64>> segs; // 存储不相交的区间[l, r]，按l有序
        int64 sum = 0, best = 0;

        for (int i = 0; i < n; ++i) {
            int64 l = b[i], r = a[i];
            sum += r - l; // 累加当前前缀的总操作次数

            // 找到可能与当前区间重叠的第一个区间
            auto it = segs.lower_bound({l, -4e18});
            if (it != segs.begin()) {
                auto prev = std::prev(it);
                if (prev->second >= l) it = prev; // 前一个区间与当前区间重叠，调整迭代器
            }

            // 合并所有重叠的区间
            while (it != segs.end() && it->first <= r && it->second >= l) {
                l = std::min(l, it->first); // 更新合并后的左端点
                r = std::max(r, it->second); // 更新合并后的右端点
                it = segs.erase(it); // 删除被合并的区间
            }

            segs.insert({l, r}); // 插入合并后的新区间
            best = std::max(best, r - l); // 更新最大区间长度

            // 输出当前前缀的答案
            cout << (sum - best) << (i + 1 == n ? '\n' : ' ');
        }
    }
    return 0;
}

关键细节

• 数据类型：使用$int64$（即$long\ long$）避免$10^9 \times 2 \times 10^5$的数值溢出。
• 区间合并效率：$\text{set}$的插入、删除、查找操作均为$O(\log m)$（$m$为当前区间数），总时间复杂度为$O(n \log n)$，满足$n \leq 2 \times 10^5$的限制。
• $\text{lower\_bound}$的作用：快速定位第一个左端点$\geq l$的区间，减少合并的遍历次数。

四、复杂度分析

• 时间复杂度：单组测试用例$O(n \log n)$，所有测试用例总复杂度$O(N \log N)$（$N$为所有测试用例的$n$之和）。
• 空间复杂度：$O(n)$，用于存储数组和区间集合。

五、示例验证

假设输入：

1
3
5 7 9
2 3 4

• $k=1$：$a[1]=5, b[1]=2$，区间$[2,5]$，$sum=3$，$best=3$，答案$3-3=0$。
• $k=2$：$a[2]=7, b[2]=3$，区间$[2,5]$和$[3,7]$合并为$[2,7]$，$sum=3+4=7$，$best=5$，答案$7-5=2$。
• $k=3$：$a[3]=9, b[3]=4$，区间$[2,7]$和$[4,9]$合并为$[2,9]$，$sum=7+5=12$，$best=7$，答案$12-7=5$。 输出：0 2 5，符合逻辑。