标签：le 06 题解 sum KDOI 补题 500005 ll

「KDOI-06-S」

A.「KDOI-06-S」消除序列

赛时写了一个 \(O(nq)\) 的线性 DP，喜提 60 分。

注意到如果操作 1 被使用，则一定只会使用一次，而且在最优策略中一定是第一次使用操作 1。则我们可以通过以下方式进行操作，使序列满足条件：
首先执行 \(a_i\) 和 \(\sum^{j \le i,i \in P}_{j = 1} c_j\) 使前 \(i\) 个元素符合条件，然后执行 \(\sum_{j = i + 1}^{j \le n, j \not \in P} b_i\) 使 \([i+1, n]\) 符合条件。
考虑如何计算：\(\sum_{j = i + 1}^{j \le n, j \not \in P} b_j = \sum_{j = i + 1}^{j \le n} b_i - \sum_{j = i + 1}^{j \le n, j \in P} b_j\) ，两项都可以后缀和维护，则原式 \(=\)

\[(a_i + \sum^{j \le i,i \in P}_{j = 1} c_j) + (\sum_{j = i + 1}^{j \le n} b_j - \sum_{j = i + 1}^{j \le n, j \in P} b_j) \\ = (a_i + \sum_{j = i + 1}^{j \le n} b_j) + (\sum^{j \le i,i \in P}_{j = 1} c_j - \sum_{j = i + 1}^{j \le n, j \in P} b_j) \]

后两项对于同一段 \([p_i,p_{i+1})\) 相同，前两项最小值可以 ST 表或者线段树维护。所以可以枚举每一段，每次做到每次询问复杂度为 \(O(m)\) 或者 \(O(m \log n)\)，足以通过本题。
容易证明最优解的操作一定符合这种方式，因为这种方式没有重复操作。
参考代码（code by @westernhan）：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
int n, m, q, a[500005], b[500005], c[500005], p[500005];
ll sumb[500005], sumc[500005], num[500005];
class ST
{
public:
    ll t[500005][35];
    ll logg(ll w)
    {
        ll res = -1;
        while (w)
            w >>= 1, res++;
        return res;
    }
    void init(void)
    {
        for (int i = 0; i <= n; i++)
            t[i][0] = sumb[i + 1] + a[i];
        for (int i = 1; i <= 25; i++)
            for (int j = 0; j + (1 << (i - 1)) <= n; j++)
                t[j][i] = min(t[j][i - 1], t[j + (1 << (i - 1))][i - 1]);
    }
    ll query(int l, int r)
    {
        if (l > r)
            return inf;
        int len = logg(r - l + 1);
        return min(t[l][len], t[r - (1 << len) + 1][len]);
    }
} T;
int main(void)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i); // copy 0
    for (int i = 1; i <= n; i++)
        scanf("%d", b + i); // set 0
    for (int i = n; i >= 1; i--)
        sumb[i] = sumb[i + 1] + b[i];
    for (int i = 1; i <= n; i++)
        scanf("%d", c + i); // set 1
    T.init();
    scanf("%d", &q);
    while (q--)
    {
        ll maxn = inf;
        scanf("%d", &m);
        for (int i = 1; i <= m; i++)
        {
            scanf("%d", p + i);
            sumc[i] = sumc[i - 1] + c[p[i]];
            num[i] = num[i - 1] + b[p[i]];
        }
        for (int i = 1; i <= m; i++)
        {
            ll res = 0;
            res += T.query(p[i - 1], p[i] - 1);
            res -= num[m] - num[i - 1];
            res += sumc[i - 1];
            maxn = min(maxn, res);
        }
        ll res = 0;
        res += T.query(p[m], n);
        res += sumc[m];
        maxn = min(res, maxn);
        printf("%lld\n", maxn);
    }
    return 0;
}

标签：le,06,题解,sum,KDOI,补题,500005,ll
From： https://www.cnblogs.com/JXOIer-zaochen/p/17768239.html