vjudge
标签
斜率优化，分治先考虑没有修改的情况，令 \(f(i)\) 表示前 \(i\) 个题能获得的最高得分。
那么 \(f(i) = \max(f_{i - 1}, f_j + (i - j)(i - j + 1) / 2 + s_i - s_j)(0 \le j < i, s_i 为 t_i 的前缀和)\)，显然是可以斜率优化的。
下面令 \(w(l, r) = (r - l)(r - l + 1) / 2 + s_r - s_l\)，表示如果做了第 \(l + 1 \sim r\) 个题的得分。
考虑修改，假设修改了 \(u\)。那么可以分为两种情况：
- 不做第 \(u\) 个题，分成 \(1 \sim u - 1, u + 1 \sim n\) 两端。
- 选择 \(u\)，假设有一个 \(l \le i \le r\) 的 \([l, r]\) 都做了，贡献是拆成 \(1 \sim l - 1, r + 1 \sim n\) 以及 \(l \sim r\) 三段，\(l \sim r\) 的贡献是 \(w(l, r)\)
令 \(g(i)\) 表示后 \(i\) 个题能获得的最高得分。（倒着做一遍即可。）
- 对于第一种情况，贡献为 \(f(u - 1) + g(u + 1)\)。
- 对于第二种，贡献为 \(h(i) = \max\limits_{l = 0}^{i - 1} \{ \max\limits_{r = i}^n \{ f(l) + g(r + 1) + w(l, r) \}\}\)。
那么修改其实就是令 \(h(u) +\!= t_u - x_i\) 即可。
于是接下来的问题变成了如何求 \(h(u)\)？
答案是分治！！又又又一次被分治创飞了。
理由： 因为这实际上是个区间问题，是可以尝试分治。并且可以发现对于 \(l, r\)，它的权值是固定的：\(W(l, r) = f(l) + g(r + 1) + w(l, r)\)，只是只对于 \(l \le i \le r\) 有贡献。而分治恰好能解决这个问题。（因为有跨过 \(mid\) 的限制。）
假设现在分治到了区间 \([L, R]\)，那么现在考虑跨过 \(mid\) 的区间 \([l, r]\) 对 \(h(i)\) 的贡献。
考虑 \(W(l, r)\) 对右半区间的 \(h(i)\) 的贡献，对于每个 \(mid + 1 \le r \le R\)，求出一个 \(F(r) = \max\limits_{r = L - 1}^{mid - 1} \{ W(l, r) \}\)，那么 \(F(r)\) 对于 \(h(mid + 1) \sim h(r)\) 均有贡献，即 \(F(i) \sim F(R)\) 对 \(h(i)\) 都有贡献。因为 \(W(l, r)\) 本身就是斜率优化的形式，所以这玩意也是可以用斜率优化 \(O(R - L)\) 做的。
对于左半区间做相同的操作即可（求出一个 \(F'(l)\)）。
于是我们在 \(O(R - L)\) 的时间内解决了 \([L, R]\) 的贡献，总时间复杂度：\(O(n \log n)\)。
实现方式
要做 \(4\) 遍斜率优化，还是太丑陋了。
发现 \(f, g\)/\(F, F'\) 的实现方式是类似的（几乎一样的），可以翻转整个序列做。减少到两个，也可以避免很多细节。
具体见代码。斜率优化的部分自己推一下，应该不难。
总结
从简单问题出发（不带修），得到一个弱化版的做法。加入修改后发现只有两种情况，转化为一个新的问题。然后要能敏锐的察觉到使用分治求解。
#include <bits/stdc++.h>
#define rev(i) (n - i + 1)using namespace std;
using ll = long long;
using i128 = __int128;const ll INF = ll(3e18);
const int MAXN = 3e5 + 5;struct Node {ll x, y;Node operator -(Node u) const {return {x - u.x, y - u.y};}ll get(int k) {return y - k * x;}
} p[MAXN];int n, T, top, a[MAXN], stk[MAXN];
ll f[MAXN], g[MAXN], rf[MAXN], rg[MAXN], ans[MAXN], mx[MAXN], pre[MAXN], suf[MAXN];
// ans 是题解中的 h，mx 是题解中的 F, F'bool F(int u, int x, int y) {auto t1 = p[x] - p[u], t2 = p[y] - p[u];return (i128)t1.x * t2.y > (i128)t2.x * t1.y;
}void getf(ll *f, ll *s) { // 求 f, g，s 为前缀/后缀和数组top = 1;for (int i = 1; i <= n; i++) {// 注意这个题是单调栈，非单调队列。因为要求最大值，k 又单调。for (; top > 1 && p[stk[top - 1]].get(i) > p[stk[top]].get(i); top--);f[i] = max(f[i - 1], p[stk[top]].get(i) + i * (i + 1ll) / 2 - s[i]);p[i] = {i, f[i] + s[i] + i * (i - 1ll) / 2};for (; top > 1 && F(stk[top - 1], stk[top], i); top--);stk[++top] = i;}
}void work(int l, int mid, int r, bool op, ll *f, ll *g) { // 计算跨过 mid 的区间对 h 的贡献。op 是正/反ll *s = (op ? suf : pre); top = 0; // s 的含义同 getffor (int i = l - 1; i < mid; i++) {p[i] = {i, f[i] + s[i] + i * (i - 1ll) / 2};for (; top > 1 && F(stk[top - 1], stk[top], i); top--);stk[++top] = i;}mx[r + 1] = -INF;for (int i = mid + 1; i <= r; i++) {for (; top > 1 && p[stk[top - 1]].get(i) > p[stk[top]].get(i); top--);mx[i] = g[i + 1] + p[stk[top]].get(i) - s[i] + i * (i + 1ll) / 2;}for (int i = r; i > mid; i--) {mx[i] = max(mx[i], mx[i + 1]);ll &val = ans[(op ? rev(i) : i)]; val = max(val, mx[i]);}
}void solve(int l, int r) {if (l == r) return ;int mid = (l + r) >> 1;work(l, mid, r, 0, f, g);work(rev(r), rev((mid + 1)), rev(l), 1, rg, rf); // 把所有东西都翻转过来做一遍即可。包括 f, gsolve(l, mid), solve(mid + 1, r);
}int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i], pre[i] = pre[i - 1] + a[i];}for (int i = 1; i <= n; i++) {suf[i] = suf[i - 1] + a[rev(i)];}getf(f, pre), getf(rg, suf);for (int i = 1; i <= n; i++) {rf[i] = f[i], g[i] = rg[i];}reverse(g + 1, g + n + 1);reverse(rf + 1, rf + n + 1);for (int i = 1; i <= n; i++) {ans[i] = f[i - 1] + g[i + 1] + 1 - a[i];}cin >> T, solve(1, n);for (int u, k; T--; ) {cin >> u >> k;cout << max(f[u - 1] + g[u + 1], ans[u] + a[u] - k) << '\n';}return 0;
}