题意：
你现在有n个题目可以做,第i个题目需要的时间为t[i],你要选择其中的若干题目去做.
不妨令choose[i]表示第i个题目做不做.
定义cost=∑(i<=n)∑(i<=j<=n)(∏(i<=k<=j)choose[k])−∑(i<=n)choose[i]×t[i]
有q个询问,每个询问给出两个数p,x表示询问假设把t[p]修改成x,当你任意指定choose[]的值时,最大的cost是多少.
首先不考虑询问，dp一遍，f[i]表示前i个题目获得的最大收益,f[i]=max(f[i-1],max{f[j]+(i-j)*(i-j+1)-sum[i]+sum[j]})，斜率优化，正反各做一边
考虑询问,p要么选要么不选，不选的话很好说，选的话我们需要求出必选p整个序列的最大收益。
分治，每次处理必选x(mid<=x<=r),且x所在选择区间左端点在(l,mid)，右端点在(mid,r)的答案,先求出以每个点为右端点的答案，再做一遍后缀最大值，就能求出每个x的答案。
第一次见分治还能这么用
#include<bits/stdc++.h>
#define int long long
#define N 300005
#define rev reverse
using namespace std;
int n,t[N],st[N],top,m;
int y[N],sum[N],f1[N],f2[N];
void yu(int *f)
{
f[0]=0;top=0;st[++top]=0;
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+t[i];
for(int i=1;i<=n;i++)
{
f[i]=f[i-1];
while(top>1&&y[st[top]]-y[st[top-1]]<=2*i*(st[top]-st[top-1]))top--;
f[i]=max(f[i],f[st[top]]+(i-st[top])*(i-st[top]+1)/2-sum[i]+sum[st[top]]);
y[i]=i*i-i+2*f[i]+2*sum[i];
while(top>1&&(y[st[top]]-y[st[top-1]])*(i-st[top-1])<=(y[i]-y[st[top-1]])*(st[top]-st[top-1]))top--;
st[++top]=i;
}
}
int f[N],tmp[N];
void solve(int *f1,int *f2,int l,int r)
{
if(l==r){f[l]=max(f[l],f1[l-1]+f2[l+1]-t[l]+1);return ;}
int mid=(l+r)>>1;top=0;
for(int i=l-1;i<mid;i++)
{
y[i]=i*i-i+2*f1[i]+2*sum[i];
while(top>1&&(y[st[top]]-y[st[top-1]])*(i-st[top-1])<=(y[i]-y[st[top-1]])*(st[top]-st[top-1]))top--;
st[++top]=i;
}
for(int i=mid;i<=r;i++)
{
while(top>1&&y[st[top]]-y[st[top-1]]<=2*i*(st[top]-st[top-1]))top--;
tmp[i]=f2[i+1]+f1[st[top]]-sum[i]+sum[st[top]]+(i-st[top])*(i-st[top]+1)/2;
}
for(int i=r-1;i>=mid;i--)tmp[i]=max(tmp[i],tmp[i+1]);
for(int i=mid;i<=r;i++)f[i]=max(f[i],tmp[i]);
solve(f1,f2,l,mid);solve(f1,f2,mid+1,r);
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&t[i]);
yu(f1);rev(t+1,t+n+1);
yu(f2);
rev(t+1,t+n+1);rev(f2+1,f2+n+1);
for(int i=1;i<=n;i++)f[i]=-t[i];
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+t[i];
solve(f1,f2,1,n);
rev(t+1,t+n+1);rev(f+1,f+n+1);rev(f1+1,f1+n+1);rev(f2+1,f2+n+1);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+t[i];
solve(f2,f1,1,n);
rev(t+1,t+n+1);rev(f+1,f+n+1);rev(f2+1,f2+n+1);rev(f1+1,f1+n+1);
scanf("%lld",&m);
for(int i=1;i<=m;i++)
{
int t1,t2;scanf("%lld%lld",&t1,&t2);
printf("%lld
",max(f1[t1-1]+f2[t1+1],f[t1]-t2+t[t1]));
}
return 0;
}