题目
题解
对于 (m=1) 这档分
我们可以 (dp) 然后斜率优化
具体来说就是 (f_i = f_j + frac{(i-j) imes (i-j+1)}{2} + sum[j]-sum[i])
很容易斜率优化
那么 (m=3 imes 10^5) 时
考虑 (cdq) 分治
考虑 (dp) 出一个如上定义的前缀 (f) 和同理的后缀 (g)
设 (h_x) 表示强制选 (x) 时的最大收益，(h_x = f_i+g_j-sum_{j-1}+sum_i+frac{(j-i) imes(j-i-1)}{2}(i < x <j))
这个 (O(n^2)) 显然不行
记 (F_i = f_i+frac{i imes (i-1)}{2}+sum_i，G_i = g_i + frac{i imes (i-1)}{2}-sum_{i-1})
则 (h_x = F_i + G_j - i imes j(i < x < j))
对于区间 ([l，r])，我们讨论 ([l，mid]) 的 (h) 值
对于一个 (lle xle mid)，它的 (h) 值 (i) 决策在它左边，(j) 决策 (mid) 右边
我们考虑对 (j) 决策斜率优化，(i) 递增，和 (f,g) 的算法有异曲同工之妙
然后通过一些玄学操作同理处理决策 (i)
最后答案就是 (max(f_{p-1}+g_{p+1}，h_p+a_p-x))
(Code)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
const int N = 3e5 + 5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m, a[N], Q[N];
LL sum[N], f[N], g[N], F[N], G[N], h[N], w[N];
inline double slope(LL *f, int j, int k)
{
return 1.0 * ((f[j] + (1LL * j * j - j) / 2.0 + sum[j]) - (f[k] + (1LL * k * k - k) / 2.0 + sum[k])) / (j - k);
}
inline void dp(LL *f)
{
memset(f, 0, sizeof f);
int top;
Q[top = 1] = 0;
for(register int i = 1; i <= n; i++)
{
while (top > 1 && slope(f, Q[top - 1], Q[top]) < i) --top;
f[i] = max(f[i - 1], f[Q[top]] + 1LL * (i - Q[top]) * (i - Q[top] + 1) / 2 - sum[i] + sum[Q[top]]);
while (top && slope(f, Q[top - 1], Q[top]) < slope(f, Q[top], i)) --top;
Q[++top] = i;
}
}
inline double slope(int j, int k){return 1.0 * (G[j] - G[k]) / (j - k);}
void divide(int l, int r, int p)
{
int mid = (l + r) >> 1, top = 0;
for(register int i = mid + 1; i <= r; i++)
{
while (top > 1 && slope(Q[top - 1], Q[top]) < slope(Q[top], i)) --top;
Q[++top] = i;
}
w[l - 1] = -INF;
for(register int i = l; i <= mid; i++)
{
while (top > 1 && slope(Q[top - 1], Q[top]) < i) --top;
w[i] = max(w[i - 1], F[i] + G[Q[top]] - 1LL * i * Q[top]);
}
if (p) for(register int i = l; i <= mid; i++) h[n - i + 1] = max(h[n - i + 1], w[i - 1]);
else for(register int i = l; i <= mid; i++) h[i] = max(h[i], w[i - 1]);
if (l ^ r) divide(l, mid, p), divide(mid + 1, r, p);
}
void solve()
{
for(register int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
dp(f);
reverse(a + 1, a + n + 1);
for(register int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
dp(g);
reverse(f + 1, f + n + 1);
for(register int i = 1; i <= n; i++) swap(f[i], g[i]);
for(register int i = 0; i <= n + 1; i++) F[i] = f[i] + 1LL * i * (i + 1) / 2 + sum[i], G[i] = g[i] + 1LL * i * (i - 1) / 2 - sum[i - 1];
for(register int i = 1; i <= n; i++) h[i] = -INF;
divide(0, n + 1, 1);
for(register int i = 1; i <= n; i++) swap(f[i], g[i]);
reverse(a + 1, a + n + 1), reverse(f + 1, f + n + 1), reverse(g + 1, g + n + 1);
for(register int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
for(register int i = 0; i <= n + 1; i++) F[i] = f[i] + 1LL * i * (i + 1) / 2 + sum[i], G[i] = g[i] + 1LL * i * (i - 1) / 2 - sum[i - 1];
divide(0, n + 1, 0);
}
int main()
{
freopen("genocide.in", "r", stdin);
freopen("genocide.out", "w", stdout);
scanf("%d", &n);
for(register int i = 1; i <= n; i++) scanf("%d", &a[i]);
solve();
scanf("%d", &m);
for(int p, x; m; --m)
{
scanf("%d%d", &p, &x);
printf("%lld
", max(f[p - 1] + g[p + 1], h[p] + a[p] - x));
}
}