【Hackerrank World11】Road Trip 题解

题目大意

  从左到右有 n 个城市，第 i 个城市到第 i+1 个城市的距离是 w[i]。到达第 i 个城市可以免费获得 g[i] 的油，你也可以自己另外买油，第 i 个城市的单价是 p[i]。
  现在 q 次询问，每次问 x[i] 到 y[i] 的最小花费。
  n, q<=1e5， g, p, w<=1e6

【40%】n, q<=1000

  每次询问 O(n) 的贪心。
  从 x 开始，假设不氪金最远能到 next[x]，则在 next[x] 处买油的价格就是 x 到 next[x] 的最小价格。
  以下方法都是基于该方法的优化。

【100%解法1】

  考虑从右到左枚举左端点 i，然后用线段树维护每个位置的要买的油量，以及（从 i 到每个位置的最小）油价。当然还有它们的积。

  第一个东西很好维护，就是每次你看看第 i 个点到第 i+1 个点是多油还是少油，少了的话，少多少第 i 个点就要买多少，多了的话，那就从 i 到 next[i]-1 都不用买了，然后 next[i] 这里看看少了多少就买多少。这里就是区间赋值操作。
  第二个东西的变化过程跟单调栈是一样的，所以用个单调栈维护每种价格的控制范围，于是在线段树中也是区间赋值操作。

  时间是 O(n log n)

【100%解法2】

  来个在线做法？

  贪心的时候我们每次从 i 跳到 next[i]，这样每次只跳一步很慢，我们就倍增地跳。即：从 i 向 next[i] 连边，这样会形成一棵树，那么在树上倍增地跳。
  但是对于不同的起点，树边对应的价格是不同的，所以不能直接倍增。
  再开一棵树，假设点 i 在第一棵树中往上跳到 x 价格都不会变，但是跳到 father[x] 价格就变了的话，就在第二棵树中把 i 的父亲设为 x。这样就可以先在第二棵树上倍增，剩出来的一些东西再在第一棵树上倍增。

  时间是 O(n log n)

代码

//解法1

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=2e5+5;

struct QST{
	int x,y,i;
};
bool cmpQ(const QST &a,const QST &b) {return a.x>b.x;}

int n,q0,w[maxn],g[maxn],p[maxn];
QST q[maxn];

LL tr[4*maxn],sum[4*maxn],bz[4*maxn];
bool zero[4*maxn];
void update(int k,int t)
{
	if (zero[k])
	{
		tr[t]=tr[t+1]=sum[t]=sum[t+1]=0;
		zero[t]=zero[t+1]=1;
		zero[k]=0;
	}
	if (bz[k])
	{
		bz[t]=bz[t+1]=bz[k];
		sum[t]=tr[t]*bz[k];
		sum[t+1]=tr[t+1]*bz[k];
	}
}
void tr_xg(int ty,int k,int l,int r,int x,int y,LL z)
{
	if (l==x && r==y)
	{
		if (ty)
		{
			sum[k]=tr[k]*z;
			bz[k]=z;
		} else
		{
			tr[k]=z;
			sum[k]=tr[k]*bz[k];
			if (z==0) zero[k]=1;
		}
		return;
	}
	int t=k<<1, t1=(l+r)>>1;
	update(k,t);
	if (y<=t1) tr_xg(ty,t,l,t1,x,y,z);
		else if (x>t1) tr_xg(ty,t+1,t1+1,r,x,y,z);
			else tr_xg(ty,t,l,t1,x,t1,z), tr_xg(ty,t+1,t1+1,r,t1+1,y,z);
	tr[k]=tr[t]+tr[t+1];
	sum[k]=sum[t]+sum[t+1];
}
LL tr_cx(int k,int l,int r,int x,int y)
{
	if (l==x && r==y) return sum[k];
	int t=k<<1, t1=(l+r)>>1;
	update(k,t);
	if (y<=t1) return tr_cx(t,l,t1,x,y);
		else if (x>t1) return tr_cx(t+1,t1+1,r,x,y);
			else return tr_cx(t,l,t1,x,t1)+tr_cx(t+1,t1+1,r,t1+1,y);
}

LL Ans[maxn],s[maxn];
int z[maxn][2],z0,fr[maxn]; // fr就是每个点不氪金最远走到哪里
int main()
{
	freopen("G.in","r",stdin);
	freopen("G.out","w",stdout);
	
	scanf("%d %d",&n,&q0);
	fo(i,1,n-1) scanf("%d",&w[i]);
	fo(i,1,n) scanf("%d %d",&g[i],&p[i]);
	fo(i,1,q0) scanf("%d %d",&q[i].x,&q[i].y), q[i].i=i;
	sort(q+1,q+1+q0,cmpQ);
	
	w[n]=2139062143;
	fo(i,1,n) s[i]=s[i-1]+g[i]-w[i];
	
	int wz=1;
	z[z0=1][0]=n;
	fd(i,n,1)
	{
		while (z0 && s[i-1]<=s[z[z0][0]]) z0--;
		fr[i]=z[z0][0];
		z[++z0][0]=i-1;
	}
	
	z0=0;
	int j=1;
	fd(i,n,1)
	{
		if (g[i]-w[i]>=0)
		{
			int x=fr[i];
			tr_xg(0,1,1,n,i,x,0);
			if (x+1<=n) tr_xg(0,1,1,n,x,x,s[i-1]-s[x]);
		} else
		{
			tr_xg(0,1,1,n,i,i,w[i]-g[i]);
		}
		int wz=i;
		while (z0 && p[i]<=z[z0][0]) wz=z[z0--][1];
		tr_xg(1,1,1,n,i,wz,p[i]);
		z[++z0][0]=p[i], z[z0][1]=wz;
		
		for(; j<=q0 && q[j].x==i; j++) if (i<q[j].y) Ans[q[j].i]=tr_cx(1,1,n,i,q[j].y-1);
	}
	
	fo(i,1,q0) printf("%lld\n",Ans[i]);
}