传送门

这题好神啊qwq

考虑没有询问的情况,显然是个斜率优化DP,拿个单调栈维护转移。这里,我们先预处理出前缀和后缀的DP值,分别记为$f_1[i]$和$f_2[i]$,以后要用。

假设现在第$x$个位置的值发生了更改,我们根据最终最优解里面这个位置是否被选取来讨论。如果这个位置没有被选,那答案就是$f_1[x-1]+f_2[x+1]$。否则,我们可以预处理出必选第$x$个位置时的最大得分,记为$g[x]$,则答案为$g[x]+v_0-v_{now}$,其中$v_0$表示第$x$个位置原来的值,$v_{now}$表示更改后的值。

现在问题变成了如何预处理出$g[x]$。考虑一个包含$x$的区间$[l,r]$,我们可以用$f_1[l-1]+f_2[r+1]+(r-l+1)(r-l+2)/2-(s[r]-s[l+1])$来更新$g[x]$(其中$s[x]$表示原数组的前缀和),$g[x]$的值为所有这样的区间的最大值。这个过程可以分治进行,对于每个分治区间,我们处理经过区间中点的所有$[l,r]$。首先我们把左半区间的点都加进单调栈中,然后再用跟之前DP一样的方法,依次询问以右半区间中的每个点作为区间右端点时,最大的DP值是多少。这样就可以完成对右半区间的所有$g[x]$的更新,左半区间也一样,反过来就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 300010
#define LL long long
using namespace std;

int n,m;
LL a[MAXN],s1[MAXN],s2[MAXN];
int pre[MAXN];
LL f1[MAXN],f2[MAXN];
LL ans[MAXN],temp[MAXN];

namespace Convex{
    LL xp[MAXN],yp[MAXN];
    int q[MAXN],head,tail;

    void init(){
        head=0;
        tail=-1;
    }

    void addPoint(int id,LL x,LL y){
        xp[id]=x;
        yp[id]=y;
        while(head<tail && (yp[q[tail]]-yp[q[tail-1]])*(xp[id]-xp[q[tail]]) 
                                                    <=
                           (yp[id]-yp[q[tail]])*(xp[q[tail]]-xp[q[tail-1]])) tail--;
        q[++tail]=id;
    }

    int query(int i){
        while(head<tail && (yp[q[tail]]-yp[q[tail-1]])<=(xp[q[tail]]-xp[q[tail-1]])*i) tail--;
        return q[tail];
    }
}

void init(){
    for(int i=1;i<=n;i++) s1[i]=a[i]+s1[i-1];
    for(int i=1;i<=n;i++) s2[i]=a[n-i+1]+s2[i-1];
    Convex::init();
    Convex::addPoint(0,0,0);
    for(int i=1;i<=n;i++){
        int j=Convex::query(i);
        f1[i]=max(f1[i-1],f1[j]+(LL)(i-j)*(i-j+1)/2-(s1[i]-s1[j]));
        pre[i]=j;
        if(f1[i]==f1[i-1]) pre[i]=i;
        Convex::addPoint(i,i,f1[i]+((LL)i*i-i)/2+s1[i]);
    }
    Convex::init();
    Convex::addPoint(0,0,0);
    for(int i=1;i<=n;i++){
        int j=Convex::query(i);
        f2[i]=max(f2[i-1],f2[j]+(LL)(i-j)*(i-j+1)/2-(s2[i]-s2[j]));
        Convex::addPoint(i,i,f2[i]+((LL)i*i-i)/2+s2[i]);
    }
    for(int i=1;i<=n;i++) if(i<n-i+1) swap(f2[i],f2[n-i+1]);
    for(int i=1;i<=n;i++) ans[i]=-(1LL<<60);
}

void gao(int l,int r){
    if(l==r){
        ans[l]=max(ans[l],f1[l-1]+f2[l+1]+1-a[l]);
        return;
    }
    int mid=(l+r)>>1;
    Convex::init();
    for(int i=l-1;i<mid;i++)
        Convex::addPoint(i,i,f1[i]+((LL)i*i-i)/2+s1[i]);
    for(int i=mid+1;i<=r;i++){
        int j=Convex::query(i);
        temp[i]=f2[i+1]+f1[j]+(LL)(i-j)*(i-j+1)/2-(s1[i]-s1[j]);
    }
    LL tmax=-(1LL<<60);
    for(int i=r;i>mid;i--){
        if(temp[i]>tmax) tmax=temp[i];
        if(tmax>ans[i]) ans[i]=tmax;
    }
    Convex::init();
    for(int i=r+1;i>mid+1;i--){
        int i2=r+1-i;
        Convex::addPoint(i,i2,f2[i]+((LL)i2*i2-i2)/2+s2[n-i+1]);
    }
    for(int i=mid;i>=l;i--){
        int j=Convex::query(r+1-i);
        temp[i]=f1[i-1]+f2[j]+(LL)(j-i)*(j-i+1)/2-(s1[j-1]-s1[i-1]);
    }
    tmax=-(1LL<<60);
    for(int i=l;i<=mid;i++){
        if(temp[i]>tmax) tmax=temp[i];
        if(tmax>ans[i]) ans[i]=tmax;
    }
    gao(l,mid);
    gao(mid+1,r);
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    init();
    gao(1,n);
    scanf("%d",&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        LL ans1=f1[x-1]+f2[x+1];
        LL ans2=ans[x]-y+a[x];
        printf("%lld\n",max(ans1,ans2));
    }
}