先证明一下不合法决策一定不优（%%二营长）
假设当前点为（x，y），不合法点为i，边界点为j=y-x，
设N=S[y]-S[j],M=S[j]-S[i-1].
我们要证明 A[i]*(x-y)+A[i]*i+S[y]-S[i]>A[j]*(x-y)+A[j]*j+S[y]-S[j]
左式=A[i]*(x-y+i)+N+M
=A[i]*(i-j)+N+M
右式=-j*A[j]+A[j]*j+N
=N
我们只需要证明M+A[i]*(i-j)>0
由于i在栈里，那么i+1~j的所有元素的A都比A[i]大即M>A[i]*(j-i)
得证
回到这个题最优策略一定是向左上走到某一列再往上一直走。
n*q在线暴力可做，离线按y排序，单调栈维护凸壳。
具体来说：对于i<j若A[i]>A[j] 即j的斜率小而且纵截距小，一定比i优，并且易得栈里直线的交点一定是递增的。
然后直接在交点二分即可。
1 #include<cstdio> 2 #include<algorithm> 3 #define N 500005 4 #define int long long 5 using namespace std; 6 int s[N],top,a[N],b[N],tot,sum[N],n; 7 double jk[N]; 8 double Get(int i,int j){return 1.0*(b[i]-b[j])/(a[j]-a[i]);} 9 inline int read() 10 { 11 int x=0,f=1;char c=getchar(); 12 while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} 13 while(c>='0'&&c<='9')x=x*10+c-48,c=getchar(); 14 return x*f; 15 } 16 struct query{ 17 int x,y,id; 18 inline void init(){x=read(),y=read();} 19 inline friend bool operator < (const query a,const query b){return a.y<b.y;} 20 }Q[N]; 21 int ans[N]; 22 inline void update(int pos) 23 { 24 while(top&&a[s[top]]>=a[pos])top--; 25 while(top>1&&Get(s[top],s[top-1])<Get(pos,s[top]))top--; 26 s[++top]=pos; 27 if(top>1)jk[n-top]=Get(s[top],s[top-1]); 28 return ; 29 } 30 signed main() 31 { 32 n=read(); 33 for(int i=1;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i],b[i]=i*a[i]-sum[i]; 34 int q=read(),j=1; 35 for(int i=1;i<=q;i++) Q[i].init(),Q[i].id=i; 36 sort(Q+1,Q+q+1); 37 for(int i=1;i<=q;i++) 38 { 39 while(j<=Q[i].y)update(j),++j; 40 int now=lower_bound(jk+n-top,jk+n-1,Q[i].x-Q[i].y)-jk;now=n-now; 41 ans[Q[i].id]=a[s[now]]*(Q[i].x-Q[i].y)+b[s[now]]+sum[Q[i].y]; 42 } 43 for(int i=1;i<=q;i++)printf("%lld\n",ans[i]); 44 return 0; 45 }