CF671E Organizing a Race

发表于 2020-04-10 更新于 2020-06-12 分类于题解

原发布于2020-01-14。

upd 2020-04-10: 代码写错了，被hack了，已更正

link

网上大多数都是 $O (n \log^{2} n)$ 的，不过我做法是 $O (n \log n)$ 的...

题解

首先考虑没有 $k$ 限制的情况（或者说加完之后）如何判断 $l, r$ 是否可以办比赛。

将题意中的 $g_{i}$ 用 $a_{i}$ 表示， $w_{i}$ 用 $b_{i}$ 表示。

设 $f_{i} = f_{i - 1} + a_{i - 1} - b_{i - 1}, g_{i} = g_{i - 1} + b_{i - 1} - a_{i}$ 。

那么 $l, r$ 可以办比赛当且仅当 $\begin{matrix} (1) & f_{l} = min_{l \leq i \leq r} f_{i}, g_{r} = min_{l \leq i \leq r} g_{i} \end{matrix}$

那么考虑有 $k$ 限制的情况。

如果 $a_{i} + 1$ ，那么对于 $i < j, f_{j} = f_{j} + 1$ ,对于 $i \leq j, g_{j} = g_{j} - 1$

从 $n$ 到 $1$ 枚举 $l$ ，设单调栈为 $f_{l} > f_{x_{1}} > f_{x_{2}} > f_{x_{3}} \dots (l < x_{1} < x_{2} < x_{3} \dots)$

那么为了 $l$ 到 $r$ 满足条件，肯定是 $a_{x_{i} - 1} = a_{x_{i} - 1} + f_{x_{i - 1}} - f_{x_{i}}$ 对于i升序一个一个执行直到 $l$ 能到 $r$ ，其中 $x_{0} = l$

接下来考虑 $r$ 到 $l$ 。

设 $h_{i}$ 为做完 $a_{x_{i} - 1} = a_{x_{i} - 1} + f_{x_{i - 1}} - f_{x_{i}}$ 后的 $g_{i}$ ,

显然剩下的 $a_{i}$ 增加都要给 $a_{r}$ ，那么 $r$ 能到 $l$ 当且仅当 $g_{r} - k \leq h_{i}, l \leq i < r$

如果对于 $i \leq l$ 定义 $h_{i} = \infty$ ，那么就是 $g_{r} - k \leq h_{i}, i < r$

可以在单调栈二分出 $r$ 的上界，然后在线段树上二分得到最大可行 $r$ 。

时间复杂度 $O (n \log n)$ 。

代码

已define int long long

int a[100005],b[100005],f[100005],g[100005];
int s[100005],t;
int n,k;
struct smt{
	int amn,bmn,atg;	
	int ls,rs;
	smt *l,*r;
	smt(int la,int ra){
		amn=inf;bmn=-inf;
		atg=0;
		ls=la;rs=ra;
		if(ls==rs){
			l=r=0;
		}
		else{
			int mid=(ls+rs)>>1;
			l=new smt(ls,mid);
			r=new smt(mid+1,rs);
		}
	}
	void setg(int x){
		if(ls==rs){
			amn=bmn=g[x];	
			return;
		}
		if(x<=l->rs)l->setg(x);
		else r->setg(x);
		amn=min(l->amn,r->amn);
		bmn=min(l->bmn,r->bmn);
	}
	void push_down(){
		l->atg+=atg;
		l->amn+=atg;
		r->atg+=atg;
		r->amn+=atg;
		atg=0;
	}
	void add(int la,int ra,int w){
		if(la<=ls && rs<=ra){
			atg+=w;amn+=w;
			return;
		}
		push_down();
		if(la<=l->rs)l->add(la,ra,w);
		if(ra>=r->ls)r->add(la,ra,w);
		amn=min(l->amn,r->amn);
	}
	int query(int x,int rm){
		if(ls>rm)return 0;
		if(bmn-k>x)return 0;//没加这一句话会错
		if(ls==rs)return ls;
		push_down();
		if(min(x,l->amn)>=r->bmn-k){
			int ans=r->query(min(x,l->amn),rm);
			if(ans)return ans;
		}
		return l->query(x,rm);
	}
};
smt *rt;
signed main(){
#ifdef QAQAutoMaton 
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
#endif
	read(n,k);
	rt=new smt(1,n);
	for(int i=1;i<n;++i)read(b[i]);
	for(int i=1;i<=n;++i)read(a[i]);
	for(int i=1;i<=n;++i){
		f[i]=f[i-1]+a[i-1]-b[i-1];
	}
	for(int i=1;i<=n;++i){
		g[i]=g[i-1]+b[i-1]-a[i];
	}
	int ans=0;
	for(int i=n;i;--i){
		rt->setg(i);
		while(t && f[s[t]]>=f[i]){
			if(t>1){
				rt->add(s[t-1]-1,n,f[s[t]]-f[s[t-1]]);
			}
			--t;
		}
		s[++t]=i;
		if(t>1){
			rt->add(s[t-1]-1,n,f[s[t-1]]-f[s[t]]);
		}

		s[0]=n+1;

		int l=1,r=t,mid;
		while(l<=r){
			mid=(l+r)>>1;
			if(f[i]-f[s[mid]]<=k)r=mid-1;
			else l=mid+1;
		}
		chkmax(ans,rt->query(inf,s[r]-1)-i+1);
	}
	write(ans,'\n');
	return 0;
}