@atcoder - ARC066F@ Contest with Drinks Hard

雨点打透心脏的1/2处 2023-06-01 14:56 2阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定序列 T1, T2, ... TN，你可以从中选择一些 Ti，可以选择 0 个（即不选）。

定义你选择的权值 = （满足 T\[L...R\] 都被选择的区间 \[L, R\] 的数量）-（你选择的 Ti 之和），你希望这个权值尽量大。

现在有 M 次询问，每次询问假如将 T\[Pi\] 修改成 Xi，你所能选出的最大权值。

**Constraints**  
1 <= N, M <= 3\*10^5，1 <= Ti <= 10^9 且所有 Ti 总和 <= 10^12。  
对于每组询问，满足 1 <= Pi <= N，1 <= Xi <= 10^9。

**Input**  
输入形式如下：  
N  
T1 T2 … TN  
M  
P1 X1  
P2 X2  
:  
PM XM

**Output**  
对于每组询问，输出其答案。

**Sample Input 1**  
5  
1 1 4 1 1  
2  
3 2  
3 10  
**Sample Output 1**  
9  
2

## @solution@ ##

考虑在修改 T\[Pi\] 为 Xi 后，最后的选择方案要么包含 Pi 要么不包含。  
假如不包含，则只需要在 1 ... Pi - 1 与 Pi + 1 ... N 中选择得到最大值。  
假如包含，我们需要预处理包含 Pi 的最优解，然后用这个最优解 + T\[Pi\] - Xi。

综上，我们需要处理出三个东西：第一个 f\[i\] 表示从 1 ... i 中选择的最优答案，第二个 g\[i\] 表示从 i ... N 中选择的最优答案，第三个 h\[i\] 表示必须选择 i 的最优答案。

先一步步考虑，考虑求 f\[i\]。要么不选 i 从 f\[i-1\] 转移过来；要么选择 i，我们枚举一个 j 表示我们强制选择 i + 1 ... j 中的所有数，则贡献为 f\[j\] + （\[i + 1, j\] 中的区间数量）-（\[i + 1, j\] 的 T 值之和）。  
通过预处理前缀和 S\[i\] = T\[1\] + T\[2\] + ... T\[i\]，可以将转移式写得更具体一点：  
\\\[f\[i\] = \\max(f\[i-1\], \\max\_\{0\\le j<i\}(f\[j\] + S\[j\] - S\[i\] + \\frac\{(i-j+1)\*(i-j)\}\{2\}))\\\]

上面那个转移非常斜率优化，稍微变化一下式子发现的确可以斜率优化。这里就不具体写了。  
总之，这个式子是个斜率单增且横坐标单增的斜率优化，可以使用单调栈做到 O(n) 的时间复杂度。  
而 g\[i\] 可以类似地处理。这里也不具体谈了。

现在考虑怎么求 h\[i\]。最暴力的方法是在 i 左边枚举一个左端点 l，i 右边枚举一个右端点 r，算出区间 \[l, r\] 的贡献再加上 f\[l - 1\] + g\[r + 1\]。  
考虑优化，我们发现 cdq 分治非常合适（其实我也不知道它该不该叫作cdq分治，只是感觉比较像）。

对于区间 \[left, right\]，设它的中点为 mid，我们仅考虑满足 left <= l <= mid < r <= right 的区间 \[l, r\] 对 h\[l...r\] 的贡献。  
然后递归到 \[left, mid\] 与 \[mid + 1, right\]，继续处理子问题，直到 left = right。

怎么处理呢？我们先将 \[left, mid\] 的点加入单调栈；然后从左往右扫 \[mid + 1, right\] 用斜率优化求出 \[mid + 1, right\] 内所有点作为右端点的答案；然后再从右往左扫描，扫到 x 时维护出 \[x, right\] 的最大值 tmp，用这个 tmp 更新 h\[x\]。  
再反过来将 \[mid + 1, right\] 加入单调栈，更新 \[left, mid\] 的 h 值。这个过程与上面类似，不再赘述。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int MAXN = 300000; const ll INF = (1LL<<60); ll f[MAXN + 5], g[MAXN + 5], h[MAXN + 5]; ll S[MAXN + 5], T[MAXN + 5]; ll fk(int i) {return i;} ll fx(int j) {return 2LL*j;} ll fc(int i) {return 1LL*i*i + i - 2*S[i];} ll fy(int j) {return 2*S[j] + f[j] - j + 1LL*j*j;} double fslope(int p, int q) {return 1.0*(fy(q) - fy(p)) / (fx(q) - fx(p));} ll gk(int i) {return -i;} ll gx(int j) {return -2LL*j;} ll gc(int i) {return 1LL*i*i - i + 2*S[i-1];} ll gy(int j) {return -2*S[j-1] + g[j] + j + 1LL*j*j;} double gslope(int p, int q) {return 1.0*(gy(q) - gy(p)) / (gx(q) - gx(p));} int stk[MAXN + 5], tp; int N, M; void get_dp() { f[0] = 0; stk[tp = 1] = 0; for(int i=1;i<=N;i++) { while( tp > 1 && fk(i) >= fslope(stk[tp], stk[tp-1]) ) tp--; f[i] = max(f[i - 1], fc(i) - fk(i)*fx(stk[tp]) + fy(stk[tp])); while( tp > 1 && fslope(i, stk[tp]) >= fslope(stk[tp], stk[tp-1]) ) tp--; stk[++tp] = i; } g[N + 1] = 0; stk[tp = 1] = N + 1; for(int i=N;i>=1;i--) { while( tp > 1 && gk(i) >= gslope(stk[tp], stk[tp-1]) ) tp--; g[i] = max(g[i + 1], gc(i) - gk(i)*gx(stk[tp]) + gy(stk[tp])); while( tp > 1 && gslope(i, stk[tp]) >= gslope(stk[tp], stk[tp-1]) ) tp--; stk[++tp] = i; } } ll tmp[MAXN + 5]; void divide_conquer(int l, int r) { if( l == r ) { h[l] = f[l + 1] - 2*T[l] + g[r + 1] + 2; return ; } int mid = (l + r) >> 1; divide_conquer(l, mid); divide_conquer(mid + 1, r); stk[tp = 1] = l - 1; for(int i=l;i<mid;i++) { while( tp > 1 && fk(i) >= fslope(stk[tp], stk[tp-1]) ) tp--; while( tp > 1 && fslope(i, stk[tp]) >= fslope(stk[tp], stk[tp-1]) ) tp--; stk[++tp] = i; } for(int i=mid+1;i<=r;i++) { while( tp > 1 && fk(i) >= fslope(stk[tp], stk[tp-1]) ) tp--; tmp[i] = fc(i) - fk(i)*fx(stk[tp]) + fy(stk[tp]) + g[i + 1]; } ll p = -INF; for(int i=r;i>mid;i--) { p = max(p, tmp[i]); h[i] = max(h[i], p); } stk[tp = 1] = r + 1; for(int i=r;i>mid+1;i--) { while( tp > 1 && gk(i) >= gslope(stk[tp], stk[tp-1]) ) tp--; while( tp > 1 && gslope(i, stk[tp]) >= gslope(stk[tp], stk[tp-1]) ) tp--; stk[++tp] = i; } for(int i=mid;i>=l;i--) { while( tp > 1 && gk(i) >= gslope(stk[tp], stk[tp-1]) ) tp--; tmp[i] = gc(i) - gk(i)*gx(stk[tp]) + gy(stk[tp]) + f[i - 1]; } p = -INF; for(int i=l;i<=mid;i++) { p = max(p, tmp[i]); h[i] = max(h[i], p); } } int main() { scanf("%d", &N); for(int i=1;i<=N;i++) scanf("%lld", &T[i]), S[i] = S[i - 1] + T[i]; get_dp(), divide_conquer(1, N); scanf("%d", &M); for(int i=1;i<=M;i++) { int P, X; scanf("%d%d", &P, &X); printf("%lld\n", max(f[P-1] + g[P+1], h[P] + 2*T[P] - 2*X)/2); } }

## @details@ ##

h\[i\] 值是必须要包含 i 的，所以可能为负数，给 h 初始化时应该赋值为 -inf。

话说现在 atcoder 都不办 ARC 了，ARC 已经成为了时代的眼泪。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11407452.html