P9744 题解
Wiales_Pretharp
2023-10-15 19:16:49
将一个不用维护线段树或者 ST 表之类数据结构的做法。
显然，将区间 $[1,i]$ 变为 $0$ 的操作至多只有一次（比如对于位置 $i$ 使用该决策会更划算，若存在一个位置 $j$，也需要使用将 $[1,j]$ 归零的操作，则在 $i$ 使用就没必要了），之后 $[1,i]$ 的区间内需要变为 $1$ 的部分和 $[i+1,n]$ 需要变为 $0$ 的部分只能挨个改，这一部分的代价可以前/后缀和计算。
接下来，我们只需要考虑在哪里使用这一次操作 $1$，很显然，我们可以通过枚举这一次操作得到答案，但是不一定最优，因为对于将 $[1,i]$ 置于 $0$，可能存在先将 $[1,j]$ 置 $0$ 再将 $[j + 1,i]$ 内的元素挨个归 $0$ 的代价比直接将 $[1,i]$ 归零更小。但是我们可以通过简单 DP 得到对于每一个前缀归零的最小代价。
此时，时间复杂度会爆炸，但是我们发现，若将 $[1,i]$ 置 $0$，则对于第一个大于 $i$ 的将要变为 $1$ 的位置（设其为 $j$），我们需要将 $[i+1,j]$ 也置于 $0$。继而可得，我们需要归零的前缀的末尾必然是在某一个将要变为 $1$ 的位置的前面一个位置，显然可以直接对于每个询问 $O(m)$ 枚举得到答案。时间复杂度 $O(n+mq)$
参考代码（cpp)：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5, M = 22;
int n, m, q, ans, mn[N], a[N], sum1[N], sumt[N], sum0[N]; // mn[] 是对于每一个前缀归零的最小代价；sum1[] 是将需要修改为 1 的部分的前缀，sumt[] 和 sum0[] 则是后缀，详情见下。
struct Squ {
int a, b, c;
} s[N];
signed main() {
// freopen("reserve.in", "r", stdin);
// freopen("reserve.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> s[i].a;
}
for(int i = 1; i <= n; i ++) {
cin >> s[i].b;
}
for(int i = n; i >= 1; i --) {
sumt[i] = sumt[i + 1] + s[i].b;
}
for(int i = 1; i <= n; i ++) {
cin >> s[i].c;
}
for(int i = 1; i <= n; i ++) {
mn[i] = min(mn[i - 1] + s[i].b, s[i].a);
}
cin >> q;
while(q --) {
cin >> m, ans = 0x3f3f3f3f3f3f3f3f;
if(m == 0) { // 特殊情况。
cout << mn[n] << endl;
continue;
}
for(int i = 1; i <= m; i ++) { // 计算前缀。
cin >> a[i], sum1[i] = sum1[i - 1] + s[a[i]].c;
}
for(int i = m, cnt = 0; i >= 1; i --) { // 计算后缀。
cnt += s[a[i]].b;
sum0[i] = sumt[a[i]] - cnt;
}
for(int i = 1; i < m; i ++) {
ans = min(
ans,
mn[a[i + 1] - 1] + sum1[i] + sum0[i + 1]
);
}
ans = min({ans, mn[a[1] - 1] + sum0[1], mn[n] + sum1[m]}); // 值得一提的是，也有可能会在区间末尾（即第 n 个位置）使用归零。
cout << ans << endl;
}
return 0;
}
```