下文令 \(a\) 为原题中的 \(T\)。
考虑若没有饮料,可以设 \(f_i\) 表示,考虑了前 \(i\) 道题,第 \(i\) 道题没做的最大得分。转移就枚举上一道没做的题 \(j\),那么 \([j + 1, i - 1]\) 形成一个连续段。设 \(b_i\) 为 \(a_i\) 的前缀和,可得:
拆项可得:
容易发现其为斜率优化形式,\(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)\) 的求法:
套路地,考虑分治。设当前分治区间为 \([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;
}
- Contest AtCoder Regular Drinks Hardcontest atcoder regular drinks atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest