P9744 题解

将一个不用维护线段树或者 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)：

#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;
}