注意到题目给出性质 保证答案必然存在 以及 ，因此考虑利用该性质解题。
考虑到对于所有满足 的位置 ，不如直接将其匹配掉。此时只会剩下若干个满足 的位置。
特判掉此时不存在 的位置 的情况，然后按 的值从小到大对二元组 排序。假设此时选择了 和 并将其消去，假设此时可以匹配成功，那么总代价将会减少 。为了让最后的代价和最小，肯定希望让减去的这个代价 的值尽量大。因此此时肯定会贪心的让 。
然后考虑什么时候可以把 和 消去然后剩下的匹配。容易想到贪心策略是直接按顺序两两匹配，此时需要满足条件 。于是想到经典套路：把每一个二元组 看做是一个区间 。此时前面给出的条件可以看作是第 个区间到第 个区间组成了一个连续段，而此时 的值就是这个连续段的长度。为了让这个长度最大，显然只需要找出所有连续段中最长的那一段 ，从序列中删除 和 ，剩下的部分按顺序两两匹配为最优解。
此时答案即为 减去最长连续段的长度，直接模拟这个过程可以做到 求解。
考虑到题目按顺序依次询问了所有的前缀，而从长度为 的前缀扩展到长度为 的前缀，只会增加一个区间 ，而维护的信息则是连续段。因此想到用类似颜色段均摊的方法维护当前所有的连续段，然后再开一个 map 维护当前所有连续段的长度，总时间复杂度为 可以通过该题。
代码，应该还是很可读的 >_<
// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000010;
const int inf = 1e18;
const int mod = 998244353;
inline int power(int a, int b, int c)
{
int ans = 1;
while (b)
{
if (b & 1)
ans = ans * a % c;
a = a * a % c, b >>= 1;
}
return ans;
}
inline int inversion(int x) { return power(x, mod - 2, mod); }
int a[N], b[N];
signed main()
{
cin.tie(0)->sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
cin >> b[i];
set<pair<int, int>> odt;
cout << 0 << ' ';
odt.emplace(b[1], a[1]);
map<int, int> yhb;
yhb[a[1] - b[1]] = 1;
int all = a[1] - b[1];
for (int i = 2; i <= n; ++i)
{
all += a[i] - b[i];
auto it = odt.lower_bound({b[i], 0});
int l = b[i], r = a[i];
while (it != odt.end() && it->first <= a[i] && it->second >= b[i])
l = min(l, it->first), r = max(r, it->second), ++it;
it = odt.lower_bound({b[i], 0});
if (it != odt.begin())
{
it = prev(it);
int ok = 0;
while (it->first <= a[i] && it->second >= b[i])
{
l = min(l, it->first), r = max(r, it->second);
if (it == odt.begin())
{
ok = 1;
break;
}
--it;
}
if (!ok)
++it;
while (it != odt.end() && it->first <= a[i] && it->second >= b[i])
{
int _l = it->first, _r = it->second;
if (!--yhb[_r - _l])
yhb.erase(yhb.find(_r - _l));
it = odt.erase(it);
}
}
else
{
while (it != odt.end() && it->first <= a[i] && it->second >= b[i])
{
int _l = it->first, _r = it->second;
if (!--yhb[_r - _l])
yhb.erase(yhb.find(_r - _l));
it = odt.erase(it);
}
}
++yhb[r - l];
odt.emplace(l, r);
cout << all - yhb.rbegin()->first << ' ';
}
cout << '\n';
}
return 0;
}
喜欢的话，留下你的评论吧～