很难啊啊啊！！！
bzoj5380原题，应该可以粘题面。
问题转换：
有一个n列1e9行的矩阵，每一列上都写着相同的数字Ai。
你从位置(x,y)出发每一步可以向左上方或左方走一步，最后走到第一行。
要求最小化路径上的总权值。
首先题意转化就让我挂了。。。
然后题解里一个显然的结论让我又挂了一回：最优决策是先往左上走几步，在往上一直走。
证明比较简单。因为如果你往上走了几步后再往左上走，那么一定不如先往左上走，不然就不是最优决策。
于是可以枚举转弯位置。（27%暴力）
1 #include<cstdio> 2 #include<iostream> 3 #define int long long 4 int n,q,a[500005],sum[500005],x,y,ans; 5 main(){ 6 scanf("%lld",&n); 7 for(int i=1;i<=n;++i)scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i]; 8 scanf("%lld",&q); 9 while(q--){ 10 scanf("%lld%lld",&x,&y); 11 ans=x*a[y]; 12 for(int i=1;i<y;++i)if(y-i<x)ans=std::min(ans,sum[y]-sum[i]+a[i]*(x+i-y)); 13 printf("%lld\n",ans); 14 } 15 }
可以发现，对于出发点（x，i），它在第j列转弯的话，费用是一个以x为自变量的一次函数。
我们同时把所有的直线画出来，然后对x时的直线们取最低点即可。
怎么维护这些直线呢？
首先可以证明，对于某一列上的任意x，其可能的最优解直线的A一定是递增的。
那么我们就可以离线所有询问，依次处理每一列就好，始终维护
感性理解的话就是你斜着往前走一定会找到一个A更小的再往上走，如果你跨过了更小的A走到更大的A上再往上走当然不优。。。
具体证明的话没时间写啦。。。推荐blog：https://blog.csdn.net/Rose_max/article/details/82250809
这样的话我们维护一个单调栈，栈中的直线按A递增，加入新的直线时弹栈把更大的A弹掉就好了。
但仅仅这样还不够，并没有把所有没用的直线弹掉。
考虑栈里的两条直线：
栈顶：y=x
倒数第二条：y=0.5x+0.5
现在要加入直线:y=2x-4
这三条直线满足A单调递增，那么可以把直线直接加入了？
并不是，在坐标系上画出这三条直线，我们会发现没有任何一个最小值在直线y=x上
在点（3，2）以后y=0.5x+0.5最小，以前是y=2x-4
这就是维护凸壳的事情了。。。我们通过判断新加入的直线与栈顶的后两条直线的交点位置来判定栈顶的直线还有没有用。
如果栈顶直线的交点横坐标更大，那么栈顶直线就没有用了。
及时弹栈之后我们就有了那个凸壳，现在剩下的问题就是对于已知x怎么求它在凸壳上的值了。
可以证明，从最优的那条直线往栈两边扫，费用都是单调递增的。
所以费用关于斜率是个单谷函数。三分求出所在直线即可。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define int long long 5 struct qs{int x,y,id;friend bool operator<(qs a,qs b){return a.y<b.y;}}q[500005]; 6 int n,a[500005],Q,b[500005],sum[500005],ans[500005],sta[500005]; 7 int cal(int p,int x){return a[p]*x+b[p];} 8 double jiao_dian(int p,int q){return (1.0*b[q]-b[p])/(a[p]-a[q]);} 9 signed main(){ 10 scanf("%lld",&n); 11 for(int i=1;i<=n;++i)scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i]; 12 scanf("%lld",&Q); 13 for(int i=1;i<=Q;++i)scanf("%lld%lld",&q[i].x,&q[i].y),q[i].id=i; 14 sort(q+1,q+1+Q); 15 for(int i=1,alq=1,top=0;i<=n;++i){ 16 b[i]=-sum[i-1]+a[i]*(i-1);//含义是：计算时的定值的sum做差，然后多走了i-1步（本来可以走到前面，但是在这里选择了往上走） 17 while(top&&a[sta[top]]>=a[i])top--;//栈内斜率一定递增否则不优 18 while(top>1&&jiao_dian(sta[top-1],i)<jiao_dian(sta[top],i))top--;//如果栈顶的直线在任意的x上都不是最又决策那么就pop掉 19 sta[++top]=i; 20 while(alq<=Q&&q[alq].y==i){ 21 int X=q[alq].x,Y=q[alq].y,l=lower_bound(sta+1,sta+top+1,Y-X+1)-sta,r=top-1;//找到可行的栈内区间 22 while(l<r)if(cal(sta[l+r>>1],X-Y)>cal(sta[(l+r>>1)+1],X-Y))l=(l+r>>1)+1;else r=l+r>>1;//三分单谷，X-Y即为至少要走的步数，剩下的步数在b里面 23 while(l<top&&cal(sta[l],X-Y)>=cal(sta[l+1],X-Y))l++;//后延直到最优解 24 ans[q[alq].id]=cal(sta[l],X-Y)+sum[i];alq++;//要加上斜着走的费用 25 } 26 } 27 for(int i=1;i<=Q;++i)printf("%lld\n",ans[i]); 28 }