自动搬运

查看原文

来自洛谷，原作者为

	Miko35 阿玮你又在打电动喔，去看会书好不好

搬运于2025-08-24 22:29:34，当前版本为作者最后更新于2022-07-20 11:03:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

$n+1$ 个加油站，第 $i$ 与 $i-1$ 个之间距离 $a_i$ 个单位长度，第 $i$ 个加油站加单位油量需要花费 $b_i$ 的代价。

车只能向右走，走 $1$ 单位长度要用 $1$ 单位油量，用完不能走。加油不能超过油量上限。

$m$ 组询问，每次给出 $l,r,x$ 表示一辆车从 $l$ 走到 $r$ 并且油量上限为 $x$ 需要花费的最小代价。

$1 \leq n,m,a_i,b_i \leq 2\times 10^5$，$1 \leq x \leq 10^9$。

题解

感谢 @クトリ 大师的提点 /bx

令油量上限为 $u$，有一个贪心：找到当前位置后第一个价格比它小的位置 $x$，加油至能走到 $x$ 为止；若到 $x$ 的距离 $\ge u$，则加满 $u$ 然后往后走一步。

考虑如何维护这个贪心：固定右端点，从右往左扫描左端点，维护价格递减的单调栈（为方便表述，令栈中元素是位置），栈顶即要找的位置。令当前位置为 $i$，$i$ 加入单调栈后，策略的变化是用 $b_i$ 替换从 $i$ 到栈顶的前 $u$ 个单位的油，不足则全部替换。原因是，我找到原单调栈中与 $i$ 距离 $\ge u$ 的第一个位置，到达此位置时我一定没油，后面策略就不变了。

但询问的 $u$ 不等，就要讨论单调栈每一段的贡献。具体而言，假设我此时弹出 $x$，弹出后的栈顶为 $y$：

• $u\leq x-i$：无事发生，当然无贡献。
• $x-i<u$：将 $\min(u+i,y)-x$ 单位油的价格由 $b_x$ 替换为 $b_i$，贡献 $(b_i-b_x)(\min(u+i,y)-x)$。

容易发现这是个关于 $u$ 的分段一次函数，线段树可以维护，这样就解决 Subtask 3 了。

对于区间 $[l,r]$ 的询问，我们找出 $[r-u,r]$ 中最小价格的位置 $k$，则 $k$ 处的决策一定是加满油到走到 $r$ 为止，这段路与「从 $k$ 走到最后」的决策完全一致，所以 $\operatorname{ans}(l,r)=\operatorname{ans}(l,+\infty)-\operatorname{ans}(k,+\infty)+b_k(r-k)$。

只需要将右端点固定为最右边就可以算出 $\operatorname{ans}(i,+\infty)$，时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
#define pbk emplace_back
#define Mn(x,y) (b[x]<b[y]?x:y)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
const int N=2e5+7,LG=18;
int n,m,l,r,k,w,u[N],C,S[N],*c=S;
struct BIT{
	ll t[N],R;
	void upd(int x,ll v){for(;x<=C;x+=x&-x)t[x]+=v;}
	ll qry(int x){for(R=0;x;x&=x-1)R+=t[x];return R;}
}K,B;
ll d[N],D,sd[N][LG+1],mx,b[N],st[N][LG+1],ans[N];
struct qry{
	int t,v,id;
	qry(int L,int V,int ID){t=L,v=V,id=ID;}
	void work(){
		int h=lower_bound(u+1,u+C,t)-u;
		ans[id]+=v*(B.qry(h)+t*K.qry(h));
	}
};
vector<qry>q[N];
void mdf(int i,ll l,ll r,int vl){
	int L=lower_bound(u+1,u+C,l=d[l]-d[i])-u,R=lower_bound(u+1,u+C,r=d[r]-d[i])-u;
	B.upd(L,-vl*l),B.upd(R,vl*r),K.upd(L,vl),K.upd(R,-vl);
}
signed main(){
	scanf("%d%d",&n,&m);
	FOR(i,2,n+1)scanf("%lld",d+i),sd[i][0]=d[i],d[i]+=d[i-1];
	FOR(i,1,n)scanf("%lld",b+i),st[i][0]=i;
	st[1+n][0]=1+n;
	FOR(w,1,LG)FOR(i,1<<w,1+n){
		st[i][w]=Mn(st[i][w-1],st[i-(1<<(w-1))][w-1]);
		sd[i][w]=max(sd[i][w-1],sd[i-(1<<(w-1))][w-1]);
	}
	FOR(i,1,m){
		scanf("%d%d%d",&l,&r,u+i),k=w=r,D=0;
		ROF(j,__lg(w),0)if(w-(1<<j)>=l)D=max(D,sd[w][j]),w-=(1<<j);
		if(D>u[i]){ans[i]=-1;continue;}
		q[l].pbk(u[i],1,i),w=r;
		ROF(j,__lg(w),0)if(w-(1<<j)>=l-1&&d[r]-d[w-(1<<j)+1]<=u[i]){
			k=Mn(k,st[w][j]),w-=(1<<j);
		}
		q[k].pbk(u[i],-1,i),ans[i]=b[k]*(d[r]-d[k]);
	}
	sort(u+1,u+m+1),C=unique(u+1,u+m+1)-u,*c=n+1;
	ROF(i,n+1,1){
		for(;c!=S&&b[i]<b[*c];--c)mdf(i,*c,c[-1],-b[*c]);
		mdf(i,i,*c,b[i]),*(++c)=i;
		for(qry k:q[i])k.work();
	}
	FOR(i,1,m)printf("%lld\n",ans[i]);
	return 0;
}