[DP记录]AT2274 [ARC066D] Contest with Drinks Hard
command_block
2021-05-13 15:29:50
**题意** ： Joisino 要去打 final。这场比赛中有 $n$ 道题，Joisino 做第 $i$ 道题花费的时间为 $t_i$ 。
这场比赛中，选手的做题方式是选择自己想做的题来做（可以不做），并且一定能做出来。最后，选手的得分将以如下方式计算：
$$
\text{得分} = \text{满足条件的二元组 $(l, r)$ 的个数} - \text{解决选了的题所花费的时间}
$$
其中，二元组 $(l, r)$ 需要满足的条件是：对于所有满足 $l \le i \le r$ 的 $i$ ，第 $i$ 题都做了。另外， $l$ 和 $r$ 还需满足 $1 \le l \le r \le n$ 。
主办方为参赛者提供了 $M$ 种饮料，如果 Joisino 喝了第 $i$ 种饮料，他做第 $p_i$ 题时会兴奋，做第 $p_i$ 题的时间将从 $t_{p_i}$ 变成 $x_i$ （注意 $x_i$ 不一定比 $t_{p_i}$ 小）做其它题的时间不受影响。
一位参赛者只能带一种饮料进入考场。Joisino 想知道如果他喝下了每种饮料，他的最大得分。
$n,m\leq 3\times 10^5$ ，时限$\texttt{2s}$。
------------
先不考虑饮料。
不难发现，对于一个长为 $l$ 的 AC 的题目的极大连续段，对答案的贡献为 $\dfrac{l(l+1)}{2}$。
记 $f[i]$ 表示考虑前 $i$ 题能得到的最大收益，$st_i$ 为 $t_i$ 的前缀和。
枚举最后一个极长连续段，有转移 ：
$$
\begin{aligned}
f[k]&=\max\limits_{i=0}^{k-1}\tfrac{(k-i)(k-i+1)}{2}-(st_k-st_i)+f[i]\\
&=\frac{1}{2}\max\limits_{i=0}^{k-1}(k-i)(k-i+1)-2(st_k-st_i)+2f[i]\\
&=\frac{1}{2}\bigg(k^2+k-2st_k+\max\limits_{i=0}^{k-1}-2ki+\big(i^2-i+2st_i+2f[i]\big)\bigg)
\end{aligned}
$$
观察后面的 $\max\limits_{i=0}^{k-1}-2ki+\big(i^2-i+2st_i+2f[i]\big)$ ，已经是可以斜率优化的形式。
然后考虑如何处理饮料的单点修改。
记 $f_i$ 表示只做题目 $f_{1\sim i}$ 能得到的最大收益， $g_i$ 表示只做题目 $i\sim n$ 能得到的最大收益，$h_i$ 表示必做题目 $i$ 所能得到的最大收益。
对于询问 $(p,x)$ ，分做或不做题目 $i$ 讨论，答案为 $\max\big(f_{i-1}+g_{i+1},h_i+t_i-x\big)$
$f,g$ 这俩货可以用前面的斜率优化 $\rm DP$ 预处理。
$h$ 用分治计算。
考虑包含 $i$ 的极长连续段，对于连续段 $[l,r]$ ，贡献为 ：
$$\tfrac{(r-l+1)(r-l+2)}{2}-(st_r-st_{l-1})+f_{l-1}+g_{r+1}$$
在 $solve(l,r)$ 中处理 $[l,r]$ 的所有子区间的贡献。
每次处理跨越 $mid$ 的区间对询问的贡献。
处理 $i\in(mid,r]$ 的 $h_i$ 。此时要求左端点 $\in [l,mid]$ ，右端点 $\in [p_i,r]$。
（对 $i\in [l,mid]$ 的部分，翻转序列重做即可）
记 $h'_i$ 为此时区间右端点恰好在 $i$ 的最优解。则有 ：
$$
\begin{aligned}
h_i'&=\max_{j+1\in[l,mid]}\tfrac{(i-j)(i-j+1)}{2}-(st_i-st_j)+f_j+g_{i+1}\\
&=g_{i+1}-st_i+\frac{1}{2}\bigg(i^2+i+\max_{j+1\in[l,mid]}-2ij+\big(j^2-j+2st_j+2f_j\big)\bigg)\\
\end{aligned}
$$
其中 $\max\limits_{j+1\in[l,mid]}-2ij+\big(j^2-j+2st_j+2f_j\big)$ 仍然是可以斜率优化的形式。线性求出凸壳，再线性扫描即可。
计算完成后， $h'_i$ 能向 $h_{mid+1\sim i}$ 贡献。
复杂度 $O\big((n+q)\log n\big)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 300500
using namespace std;
struct Line{
int k;ll b;
ll get(int x){return 1ll*k*x+b;}
}q[MaxN];
bool chk(Line A,Line B,Line C){
int x1=A.k-B.k,x2=C.k-B.k;
ll y1=A.b-B.b,y2=C.b-B.b;
return x1*y2-x2*y1>=0;
}
ll st[MaxN];
void calc(ll *t,ll *f,int n)
{
int top=1;q[1]=(Line){0,0};
for (int i=1;i<=n;i++){
st[i]=st[i-1]+t[i];
while(top>1&&q[top].get(i)<=q[top-1].get(i))top--;
f[i]=max(f[i-1],-st[i]+(q[top].get(i)+1ll*i*(i+1))/2);
Line now=(Line){-2*i,1ll*i*(i-1)+2*(f[i]+st[i])};
while(top>1&&chk(q[top-1],q[top],now))top--;
q[++top]=now;
}
}
ll ans[MaxN],t[MaxN],fl[MaxN],fr[MaxN],sc[MaxN];
bool flag;
void solve(int l,int r)
{
if (l==r)return ;
int mid=flag ? (l+r)>>1 : (l+r-1)>>1;
solve(l,mid);solve(mid+1,r);
int top=0;
for (int i=l-1;i<mid;i++){
Line now=(Line){-2*i,1ll*i*(i-1)+2*(st[i]+fl[i])};
while(top>1&&chk(q[top-1],q[top],now))top--;
q[++top]=now;
}
for (int i=mid+1;i<=r;i++){
while(top>1&&q[top].get(i)<=q[top-1].get(i))top--;
sc[i]=fr[i+1]-st[i]+(q[top].get(i)+1ll*i*(i+1))/2;
}
sc[r+1]=-1ll<<60;
for (int i=r;i>mid;i--)
ans[i]=max(ans[i],sc[i]=max(sc[i],sc[i+1]));
}
int n,m;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%lld",&t[i]);
calc(t,fr,n);reverse(fr+1,fr+n+1);
reverse(t+1,t+n+1);calc(t,fl,n);
for (int i=1;i<=n;i++)ans[i]=-1ll<<60;
solve(1,n);
reverse(ans+1,ans+n+1);reverse(t+1,t+n+1);
for (int i=1;i<=n;i++)st[i]=st[i-1]+t[i];
for (int i=1;i<=n;i++)swap(fl[i],fr[i]);
reverse(fl+1,fl+n+1);reverse(fr+1,fr+n+1);
flag=1;solve(1,n);
scanf("%d",&m);
for (int i=1,p,x;i<=m;i++){
scanf("%d%d",&p,&x);
printf("%lld\n",max(fl[p-1]+fr[p+1],ans[p]+t[p]-x));
}return 0;
}
```