「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_i = \sum_{j = i + 1}^{j \le n} b_i - \sum_{j = i + 1}^{j \le n, j \in P} b_i\) ，两项都可以后缀和维护，则原式 \(=\)
\[(a_i + \sum^{j \le i,i \in P}_{j = 1} c_j) + (\sum_{j = i + 1}^{j \le n} b_i - \sum_{j = i + 1}^{j \le n, j \in P} b_i) \\ = (a_i + \sum_{j = i + 1}^{j \le n} b_i) + (\sum^{j \le i,i \in P}_{j = 1} c_j - \sum_{j = i + 1}^{j \le n, j \in P} b_i)
\]
后两项对于同一段 \([p_i,p_{i+1})\) 相同，前两项最小值可以 ST 表或者线段树维护。所以可以枚举每一段，每次做到每次询问复杂度为 \(O(m)\) 或者 \(O(m \log n)\)，足以通过本题。
容易证明最优解的操作一定符合这种方式，因为这种方式没有重复操作。