先证明一下不合法决策一定不优(%%二营长)

假设当前点为(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 }
View Code
01-15 05:21