题解 P7408 [JOI 2021 Final] ダンジョン 3
Miko35
·
·
题解
题意
车只能向右走，走 $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$。
### 题解
感谢 @[クトリ](https://www.luogu.com.cn/user/25251) 大师的提点 /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)$。
```cpp
#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;
}
```