CF671E Organizing a Race

原发布于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\)可以办比赛当且仅当 \[f_l=\min _{l\leq i \leq r} f_i,g_r=\min _{l\leq i \leq r} g_i\]

那么考虑有\(k\)限制的情况。

如果\(a_i+1\)，那么对于\(i\lt j,f_j=f_j+1\),对于\(i\le j,g_j=g_j-1\)

从\(n\)到\(1\)枚举\(l\)，设单调栈为\(f_l\gt f_{x_1}\gt f_{x_2}\gt f_{x_3}\ldots(l\lt x_1\lt x_2\lt x_3\ldots)\)

那么为了\(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\le i\lt r\)

如果对于\(i\le l\)定义\(h_i=\infty\)，那么就是\(g_r-k\leq h_i,i\lt 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;
}