[CF671E] Organizing a Race

2019/03/31 19:13
阅读数 26

题目大意

有$n$个加油站排成一行,编号为$1\sim n$ ,$i$与$i+1$间有一条长为$w_i$千米的道路。 一辆汽车在经过加油站$i$时会得到$g_i$升汽油 , 假设汽车每行驶一千米需要消耗一升汽油。 现在要求选定两个合法的加油站 $i$ 、$j$, 且 $i\le j$,使得一辆没有油的汽车能从$i$出发行驶到 $j$,也能从$j$出发行驶到$i$ 。 你有$K$次操作,每次操作能使选定一个$i$ , 使$g_i$增加 $1$。 对于所有合法的$i$与$j$ ,求$j − i + 1$的最大值。数据范围:$n\leq 10^5$ , $w,g,K\leq 10^9$。

题解

化简限制条件

令$pre_i = pre_{i-1} + g_i - w_i$、$suf_i = suf_{i-1} + g_i - w_{i-1}$。 考虑枚举一个左端点$l$,如何判断一个右端点$r$合法? 首先保证能够从$l$走到$r$,即对于$k\in [l,r)$,满足$pre_{k-1}-pre_{l-1} \ge 0$,贪心能走就走即可。 设只满足从左走到右需要付出的代价为$cost_{l,r}$,设付出这些代价后,$suf$值变成了$suf'$。 为了满足从右边能够走到左边,显然贪心只只在右端点进行改造是最优的。 故一个$[l,r]$合法的条件为:$cost_{l,r}\leq K$,$max(suf'k | k\in [l,r)) - suf{l}' + cost_{l,r} \leq K$。

一些预处理与转化

注意到若不付出代价且$i$不能走到$j$(只考虑左到右的限制),则$pre_{j-1} - pre_{i-1} < 0$。 即$pre_{i-1} > pre_{j-1}$,令$nxt_i = min(j|pre_{i-1} > pre_{j-1})$,则$i\to nxt_i$形成了一棵树型结构。 我们在这棵树上进行遍历,当$dfs$到$u$时,就可以知道$cost_{u,v} = pre_{u-1}-pre_{t-1}$,其中$t$为$u$满足$t\leq v$的最浅祖先。 当位于$u$点时,我们计算以$u$为左端点的最大答案。 那么即求$Ans_u = max(r|cost_{l,r}\leq K,max(suf_k'|k\in [u,r))-suf'k+cost_{u,r})$。

线段树维护什么

考虑用线段树支持上述操作,对于区间$[l,r]$的线段树结点,维护:

  • $Minp_{l,r} = min(-suf_k' + cost_{u,k}|k\in [l,r])$,可以发现这个值对于任意$u$都不变。 因为$dfs$过程中,若从$u\to v$,则$suf'k$与$cost{u,k}$的变化量都是$+ pre_{v-1}-pre_{u-1}$,所以预处理即可。 令$P_{l,r} = min(-suf_k|k\in [l,r]) = Minp_{l,r}$。
  • $Maxs_{l,r} = max(suf_k' | k\in [l,r])$,维护就是普通区间加法,区间求$max$。
  • $ans_{l,r} = min(\ max(suf_k'|k\in [l,j)) + P_j\ |\ j\in (mid,r]\ )$。

下面详细介绍一下如何维护$ans_{l,r}$、以及利用这些东西在$dfs$到$u$时查询$Ans_u$。

数组$ans$的维护

考虑如何求$ans_{L,R} = min(\ max(suf_k'|k\in [L,j)) + P_j\ |\ j\in (mid,R]\ )$。 类似线段树维护单调栈,考虑递归处理。 设当前处理到$[l,r]$,令$x = max(suf'k | k\in [L,l))$,令$y = Maxs{l,mid}$。

  • 若$x\ge y$,则$j\in [l,mid)$中的$max(suf_k'|k\in [L,j)) = x$,答案为$x + minp_{l,mid}$。 递归处理$(mid,r]$的答案。
  • 若$x \leq y$,则$x$对$(mid,r]$的答案无影响,即$j\in (mid,r]$的答案为$ans_{l,r}$。 递归处理$[l,mid]$的答案。

每次$PushUp$的复杂度为$O(logn)$,故修改复杂度为$O(nlog^2n)$。

查询答案$Ans_u$

首先二分得到最大的满足$cost_{u,r}\leq K$的$pr$,把$[pr,n]$的$suf'$加上$inf$,即把$(pr,n]$剔除出去。 然后把$[1,u)$的$suf'$都加上$-inf$,消去它们对答案的影响。 上面哪些都是为了方便操作,下面来看具体如何查询。 设当前查询区间$[L,R]$的答案,令$x = max(suf'k|k\in [1,L))$,令$y = Maxs{L,mid}$。

  • 若$x\ge y$,则$j\in [L,mid]$的$max(suf'_k|k\in [1,j)) = x$为定值,线段树上二分即可。 递归处理$(mid,R]$的答案。
  • 若$x\leq y$,则$x$对$(mid+1,R]$的答案无影响,若$ans_{l,r}\leq K$则递归$(mid,R]$,否则递归$[L,mid]$。

单次查询的最坏复杂度为$O(log^2n)$,故查询总复杂度为$O(nlog^2n)$。

实现代码

#include<bits/stdc++.h>
#define IL inline
#define _ 200005
#define ll long long
#define RG register
using namespace std ;

IL ll gi() {
	RG ll data = 0 , fu = 1 ; RG char ch = getchar() ;
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar() ; if(ch == '-') fu = -1 , ch = getchar() ;
	while('0' <= ch && ch <= '9') data = (data << 1) + (data << 3) + (ch ^ 48) , ch = getchar() ; return fu * data ; 
}

const ll inf = 1e16 ; 

int stk[_] , nxt[_] , n , K ; ll pre[_] , suf[_] , W[_] , g[_] , root ; int Ans ;
vector<int> edge[_] ;  

namespace Seg {
	ll Minp[_ << 2] , Maxs[_ << 2] , ans[_ << 2] , tag[_ << 2] ; 	
	IL void Add(int o , ll v) {
		Maxs[o] += v ; tag[o] += v ; ans[o] += v ; 
		return ; 
	}
	IL void PushDown(int o) {
		if(tag[o] == 0) return ; 
		Add(o << 1 , tag[o]) ; Add(o << 1 | 1 , tag[o]) ; tag[o] = 0 ;
	}
	ll Calc(int o , int l , int r , ll x) {
		if(l == r) return x + Minp[o] ; int mid = (l + r) >> 1 ; 
		PushDown(o) ; 
		ll y = Maxs[o << 1] ;
		if(x >= y) return min(x + Minp[o << 1] , Calc(o << 1 | 1 , mid + 1 , r , x)) ;
		else return min(ans[o] , Calc(o << 1 , l , mid , x)) ; 
	}
	IL void PushUp(int o , int l , int r) {
		Maxs[o] = max(Maxs[o << 1] , Maxs[o << 1 | 1]) ;
		int mid = (l + r) >> 1 ;  
		ans[o] = Calc(o << 1 | 1 , mid + 1 , r , Maxs[o << 1]) ;  
	}
	void Build(int o , int l , int r) {
		if(l == r) {
			Minp[o] = -suf[l] ; Maxs[o] = suf[l] ; ans[o] = 0 ;
			return ; 
		}
		int mid = (l + r) >> 1 ; 
		Build(o << 1 , l , mid) ; Build(o << 1 | 1 , mid + 1 , r) ; PushUp(o , l , r) ; 
		Minp[o] = min(Minp[o << 1] , Minp[o << 1 | 1]) ;
	}
	IL void Insert(int o , int l , int r , int ql , int qr , ll v) {
		if(ql <= l && r <= qr) {Add(o , v) ; return ; }
		int mid = (l + r) >> 1 ;
		PushDown(o) ; 
		if(ql <= mid) Insert(o << 1 , l , mid , ql , qr , v) ;
		if(qr  > mid) Insert(o << 1 | 1 , mid + 1 , r , ql , qr , v) ; 
		PushUp(o , l , r) ;
	}
	int Solve(int o , int l , int r , ll x) {
		if(l == r) return x + Minp[o] <= K ? l : 0 ;
		int mid = (l + r) >> 1 ; 
		PushDown(o) ;
		if(x + Minp[o << 1 | 1] <= K) return Solve(o << 1 | 1 , mid + 1 , r , x) ; 
		else return Solve(o << 1 , l , mid , x) ;
	}
	int Query(int o , int l , int r , ll x) {
		if(l == r) {
			return x + Minp[o] <= K ? l : 0 ; 
		}
		int mid = (l + r) >> 1 ; PushDown(o) ; 
		ll y = Maxs[o << 1] ;
		int ret = 0 ; 
		if(x >= y) {
			ret = Query(o << 1 | 1 , mid + 1 , r , x) ; 
			if(x + Minp[o] <= K) ret = max(ret , Solve(o << 1 , l , mid , x)) ; 
		}
		else if(x <= y) {
			if(ans[o] <= K) ret = Query(o << 1 | 1 , mid + 1 , r , y) ;
			else ret = Query(o << 1 , l , mid , x) ; 
		}
		return ret ; 
	}
}

IL void Pre() {
	stk[0] = 0 ; 
	for(int i = n; i >= 1; i --) {
		while(stk[0] && pre[i - 1] <= pre[stk[stk[0]] - 1]) -- stk[0] ;
		nxt[i] = stk[0] ? stk[stk[0]] : n + 1 ;
		stk[++ stk[0]] = i ;
	}
	root = n + 1 ; nxt[root] = n + 1 ;
	for(int i = 1; i <= n; i ++) edge[nxt[i]].push_back(i) ; return ;  
}
IL int Bipart(int x) {
	int l = 2 , r = stk[0] , ret = 1 ; 
	while(l <= r) {
		int mid = (l + r) >> 1 ; 
		if(pre[x - 1] - pre[stk[mid] - 1] <= K) ret = mid , r = mid - 1 ; 
		else l = mid + 1 ; 
	}
	return stk[ret - 1] - 1 ; 
}
void Dfs(int u , int From) {
	stk[++ stk[0]] = u ; 
	if(nxt[u] <= n) Seg::Insert(1 , 1 , n , nxt[u] - 1 , n , pre[u - 1] - pre[nxt[u] - 1]) ;
	if(u <= n) { 
		int r = Bipart(u) ;
		if(r < n) Seg::Insert(1 , 1 , n , r , n , inf) ; if(u != 1) Seg::Insert(1 , 1 , n , 1 , u - 1 , -inf) ; 
		Ans = max(Ans , Seg::Query(1 , 1 , n , -inf) - u + 1) ;
		if(r < n) Seg::Insert(1 , 1 , n , r , n , -inf) ; if(u != 1) Seg::Insert(1 , 1 , n , 1 , u - 1 , inf) ;
	}
	for(auto v : edge[u]) if(v != From) Dfs(v , u) ;
	-- stk[0] ; 
	if(nxt[u] <= n) Seg::Insert(1 , 1 , n , nxt[u] - 1 , n , pre[nxt[u] - 1] - pre[u - 1]) ; 	
}

int main() {
	n = gi() ; K = gi() ;
	for(int i = 1; i < n; i ++) W[i] = gi() ; W[n] = inf ; 
	for(int i = 1; i <= n; i ++) g[i] = gi() ;
	for(int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + g[i] - W[i] ;  
	for(int i = 1; i <= n; i ++) suf[i] = suf[i - 1] + g[i] - W[i - 1] ;
	Pre() ;
	Seg::Build(1 , 1 , n) ; 
	stk[0] = 0 ; Dfs(root , 0) ; 
	cout << Ans << endl ;  return 0 ;
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部