下文令 \(a\) 为原题中的 \(T\)。
考虑若没有饮料，可以设 \(f_i\) 表示，考虑了前 \(i\) 道题，第 \(i\) 道题没做的最大得分。转移就枚举上一道没做的题 \(j\)，那么 \([j + 1, i - 1]\) 形成一个连续段。设 \(b_i\) 为 \(a_i\) 的前缀和，可得：
\[f_i = \max\limits_{j = 0}^{i - 1} \{ f_j + \frac{(i - j)(i - j - 1)}{2} - b_{i - 1} + b_j \} \]拆项可得：
\[f_i - \frac{i(i - 1)}{2} + b_{i - 1} = \max\limits_{j = 0}^{i - 1} \{ f_j + \frac{j(j + 1)}{2} + b_j - ij \} \]容易发现其为斜率优化形式，\(f_i - \frac{i(i - 1)}{2} + b_{i - 1}\) 是截距，\(f_j + \frac{j(j + 1)}{2} + b_j\) 是纵坐标，\(i\) 是斜率，\(j\) 是横坐标。注意到斜率和横坐标都单增，所以需要使用单调栈维护上凸包。
考虑若有饮料，设饮料把 \(a_x\) 变成 \(y\)。分类讨论是否使用饮料。再求一个 \(g_i\) 表示考虑了第 \(i\) 道题到第 \(n\) 道题，第 \(i\) 道题没做的最大得分。
若没使用饮料，答案是 \(f_x + g_x\)；
若使用饮料，答案是 \(h_x + a_x - y\)。其中 \(h_i\) 表示必须做第 \(i\) 道题的最大得分。
考虑如何求 \(h_i\)。有一个单次 \(O(n^2)\) 的求法：
\[h_i = \max\limits_{l < i < r} \{ f_l + g_r + \frac{(r - l)(r - l - 1)}{2} - b_{r - 1} + b_l \} \]套路地，考虑分治。设当前分治区间为 \([L, R]\)，\(mid = \left\lfloor\frac{L + R}{2}\right\rfloor\)。考虑 \(l \in [L, mid], r \in [mid + 1, R]\)，对 \(i \in (L, R)\) 造成的贡献。分类讨论 \(i\) 在哪半边，例如若 \(i \in (L, mid], l \in [L, i - 1], r \in [mid + 1, R]\)，就求一个 \([mid + 1, R]\) 的凸包，然后遍历 \(l\)，双指针遍历凸包即可。
时间复杂度为 \(O(n \log n)\)。
code
// Problem: F - Contest with Drinks Hard
// Contest: AtCoder - AtCoder Regular Contest 066
// URL: https://atcoder.jp/contests/arc066/tasks/arc066_d
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 300100;
ll n, m, a[maxn], b[maxn], f[maxn], g[maxn], h[maxn], stk[maxn], top;
struct node {
ll x, y;
node(ll a = 0, ll b = 0) : x(a), y(b) {}
} c[maxn];
inline node operator + (const node &a, const node &b) {
return node(a.x + b.x, a.y + b.y);
}
inline node operator - (const node &a, const node &b) {
return node(a.x - b.x, a.y - b.y);
}
inline ll operator * (const node &a, const node &b) {
return a.x * b.y - a.y * b.x;
}
void dfs(int l, int r) {
if (l == r) {
return;
}
int mid = (l + r) >> 1, tot = 0, top = 0;
for (int i = mid + 1; i <= r; ++i) {
c[++tot] = node(i, g[i] + 1LL * i * (i - 1) / 2 - b[i - 1]);
}
for (int i = 1; i <= tot; ++i) {
while (top > 1 && (c[i] - c[stk[top - 1]]) * (c[stk[top]] - c[stk[top - 1]]) <= 0) {
--top;
}
stk[++top] = i;
}
ll mx = -1e18;
// printf("l, r: %d %d %d\n", l, mid, r);
for (int i = l, j = top; i <= mid; ++i) {
while (j > 1 && (c[stk[j]].y - c[stk[j - 1]].y) <= (c[stk[j]].x - c[stk[j - 1]].x) * i) {
--j;
}
int k = stk[j] + mid;
h[i] = max(h[i], mx);
// printf("%d %d %lld\n", i, k, f[i] + g[k] + 1LL * (k - i) * (k - i - 1) / 2 - b[k - 1] + b[i]);
mx = max(mx, f[i] + g[k] + 1LL * (k - i) * (k - i - 1) / 2 - b[k - 1] + b[i]);
}
tot = top = 0;
for (int i = l; i <= mid; ++i) {
c[++tot] = node(i, f[i] + 1LL * i * (i + 1) / 2 + b[i]);
}
for (int i = 1; i <= tot; ++i) {
while (top > 1 && (c[i] - c[stk[top - 1]]) * (c[stk[top]] - c[stk[top - 1]]) <= 0) {
--top;
}
stk[++top] = i;
}
mx = -1e18;
for (int i = r, j = 1; i > mid; --i) {
while (j < top && (c[stk[j + 1]].y - c[stk[j]].y) >= (c[stk[j + 1]].x - c[stk[j]].x) * i) {
++j;
}
int k = stk[j] + l - 1;
h[i] = max(h[i], mx);
mx = max(mx, f[k] + g[i] + 1LL * (i - k) * (i - k - 1) / 2 - b[i - 1] + b[k]);
}
dfs(l, mid);
dfs(mid + 1, r);
}
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
b[i] = b[i - 1] + a[i];
}
scanf("%lld", &m);
stk[++top] = 0;
for (int i = 1; i <= n; ++i) {
while (top > 1 && (c[stk[top]].y - c[stk[top - 1]].y) <= (c[stk[top]].x - c[stk[top - 1]].x) * i) {
--top;
}
int j = stk[top];
f[i] = f[j] + 1LL * (i - j) * (i - j - 1) / 2 - b[i - 1] + b[j];
c[i] = node(i, f[i] + 1LL * i * (i + 1) / 2 + b[i]);
while (top > 1 && (c[i] - c[stk[top - 1]]) * (c[stk[top]] - c[stk[top - 1]]) <= 0) {
--top;
}
stk[++top] = i;
}
reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) {
b[i] = b[i - 1] + a[i];
}
mems(stk, 0);
top = 0;
stk[++top] = 0;
for (int i = 1; i <= n; ++i) {
while (top > 1 && (c[stk[top]].y - c[stk[top - 1]].y) <= (c[stk[top]].x - c[stk[top - 1]].x) * i) {
--top;
}
int j = stk[top];
g[i] = g[j] + 1LL * (i - j) * (i - j - 1) / 2 - b[i - 1] + b[j];
c[i] = node(i, g[i] + 1LL * i * (i + 1) / 2 + b[i]);
while (top > 1 && (c[i] - c[stk[top - 1]]) * (c[stk[top]] - c[stk[top - 1]]) <= 0) {
--top;
}
stk[++top] = i;
}
reverse(a + 1, a + n + 1);
reverse(g + 1, g + n + 1);
for (int i = 1; i <= n; ++i) {
b[i] = b[i - 1] + a[i];
}
mems(h, -0x3f);
dfs(0, n + 1);
// for (int i = 1; i <= n; ++i) {
// printf("h[%d] = %lld\n", i, h[i]);
// }
// for (int i = 1; i <= n + 1; ++i) {
// printf("g[%d] = %lld\n", i, g[i]);
// }
while (m--) {
ll x, y;
scanf("%lld%lld", &x, &y);
printf("%lld\n", max(f[x] + g[x], h[x] + a[x] - y));
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}