自动搬运

查看原文

来自洛谷，原作者为

	VainSylphid 美しい音色で世界が鳴った

搬运于2025-08-24 23:04:41，当前版本为作者最后更新于2024-10-10 16:42:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简单题，怎么没有人写题解。

考虑贪心，如果对于城市 $x$ 到右边的第一个 $p_y<p_x$ 的城市 $y$ 的距离不超过 $V$，那么应该在城市 $x$ 加油到刚好能跑到城市 $y$，否则我们在城市 $x$ 加满油，向右跑到油耗尽的位置（注意油耗尽的位置不一定在某个城市），然后再考虑在这段路上找一个油价 $p_y$ 最低的城市 $y$（这个城市的油价 $p_y$ 一定比 $p_x$ 高），然后我们计算从 $y$ 出发的答案，减去在城市 $y$ 到油耗尽的位置这一段的贡献（因为在城市 $x$ 已经加了这一段的油）即可。

那么还剩两个问题，第一个是刚开始时油箱中的油：如果这些油已经足够跑到终点，那么此时特判答案为 $0$。否则，我们计算为了前 $v$ 公里的路而加的油的贡献，从 $v=0$ 的答案减去即可，因为这一段路所用的油价格一定是单调不增的。

第二个问题是怎么维护暴力跳的过程，这个过程类似于在树上跳父亲，可以用倍增之类的东西维护，我的实现是倍增，需要注意一下空间。时间复杂度当然是 $O((n+m)\log n)$ 的。我的代码常数怎么这么大。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,V,p[1000005],l[1000005],s[1000005],stk[1000005],tp;
ll to[1000005],g[20][1000005],f[20][1000005],w[20][1000005],lg[1000005];
ll query(ll x,ll y)
{
	ll t = lg[y - x + 1];
	if(p[f[t][x]] >= p[f[t][y - (1 << t) + 1]])
		return f[t][y - (1 << t) + 1];
	return f[t][x];
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&V);
	for(ll i = 2;i <= n;i++)
		lg[i] = lg[i >> 1] + 1;
	for(ll i = 1;i <= n;i++)
		scanf("%lld",&p[i]);
	for(ll i = 1;i < n;i++)
		scanf("%lld",&l[i]);
	for(ll i = 2;i <= n;i++)
		s[i] = s[i - 1] + l[i - 1];
	to[n] = n;
	for(ll i = n - 1;i;i--)
	{
		to[i] = to[i + 1];
		while(s[to[i]] - s[i] > V)
			to[i]--;
	}
	stk[++tp] = n + 1;
	for(ll i = n;i;i--)
	{
		while(p[i] < p[stk[tp]])
			stk[tp--] = 0;
		to[i] = min(to[i],stk[tp]),stk[++tp] = i;
	}
	for(ll i = 1;i <= n;i++)
		f[0][i] = i;
	for(ll j = 1;j < 20;j++)
		for(ll i = 1;i + (1 << j) - 1 <= n;i++)
		{
			if(p[f[j - 1][i]] < p[f[j - 1][i + (1 << (j - 1))]])
				f[j][i] = f[j - 1][i];
			else
				f[j][i] = f[j - 1][i + (1 << (j - 1))];
		}
	for(ll i = 1;i <= n;i++)
		if(p[to[i]] > p[i])
			g[0][i] = query(i + 1,to[i]);
		else
			g[0][i] = to[i];
	for(ll i = 1;i <= n;i++)
		if(p[to[i]] > p[i])
			f[0][i] = V * p[i],w[0][i] = s[i] + V;
		else
			f[0][i] = (s[to[i]] - s[i]) * p[i],w[0][i] = s[to[i]];
	for(ll j = 1;j < 20;j++)
		for(ll i = 1;i <= n;i++)
		{
			g[j][i] = g[j - 1][g[j - 1][i]];
			f[j][i] = f[j - 1][i] + f[j - 1][g[j - 1][i]] - (w[j - 1][i] - s[g[j - 1][i]]) * p[g[j - 1][i]];
			w[j][i] = w[j - 1][g[j - 1][i]];
		}
	for(ll i = 1;i <= m;i++)
	{
		ll x,y,v;
		scanf("%lld%lld%lld",&x,&y,&v);
		if(s[y] - s[x] <= v)
		{
			printf("0\n");
			continue;
		}
		ll s1 = 0,s2 = 0;
		ll tmp = x,wl = s[x];
		for(ll j = 19;j >= 0;j--)
			if(w[j][tmp] - s[x] <= v)
				s1 = s1 + f[j][tmp] - (wl - s[tmp]) * p[tmp],wl = w[j][tmp],tmp = g[j][tmp];
		s1 += p[tmp] * (s[x] + v - wl);
		tmp = x,wl = s[x];
		for(ll j = 19;j >= 0;j--)
			if(w[j][tmp] < s[y])
				s2 = s2 + f[j][tmp] - (wl - s[tmp]) * p[tmp],wl = w[j][tmp],tmp = g[j][tmp];
		s2 += p[tmp] * (s[y] - wl);
		printf("%lld\n",s2 - s1);
	}
	return 0;
}