题解：P11151 [THUWC 2018] 明天的太阳会照常升起

· · 题解

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

考虑贪心，如果对于城市 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;
}