自动搬运

查看原文

来自洛谷，原作者为

	Genius_Star 跟你爆了

搬运于2025-08-24 22:54:52，当前版本为作者最后更新于2024-02-02 09:34:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

考虑线段树维护：

• $sum$ 区间内活着的 bot 个数。

• $Max_1$ 区间内喝“原味冰红茶”最后连续喝的数量的最大值。

• $Max_2$ 区间内喝“热带风味冰红茶”最后连续喝的数量的最大值。

• $tag_1$ 区间覆盖“原味冰红茶”最后连续喝的数量的懒标记。

• $tag_2$ 区间覆盖“热带风味冰红茶”最后连续喝的数量的懒标记。

• $tag_3$ 区间增加“原味冰红茶”最后连续喝的数量的懒标记。

• $tag_4$ 区间增加“热带风味冰红茶”最后连续喝的数量的懒标记。

每次操作 $1$ 时：

• 将 $[l,r]$ 区间内喝“热带风味冰红茶”最后连续喝的数量覆盖为 $0$。

• 将 $[l,r]$ 区间内喝“原味冰红茶”最后连续喝的数量增加 $k$。

• 将 $[1,l-1]$ 区间内喝“原味冰红茶”最后连续喝的数量覆盖为 $0$。

• 将 $[r+1,n]$ 区间内喝“原味冰红茶”最后连续喝的数量覆盖为 $0$。

• 将 $[1,l-1]$ 区间内喝“热带风味冰红茶”最后连续喝的数量增加 $k$。

• 将 $[r+1,n]$ 区间内喝“热带风味冰红茶”最后连续喝的数量增加 $k$。

每次操作 $2$ 时：

• 如果 $[l,r]$ 的 $sum$ 为 $0$（即都死完了），退出。

• 如果 $[l,r]$ 的 $\max(Max_1,Max_2)<k$，则这个区间最大的都没有连续喝 $k$ 瓶相同口味的冰红茶，退出。

• 否则线段树一直分，跳到单点为止，直接修改。

每次操作 $3$ 时：

• 输出 $root$ 的 $sum$ 即可。

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

常数略大，谨慎使用。

提交记录 666ms。

细节：

对于区间覆盖标记 $tag_1$ 和 $tag_2$，下传时也要将儿子的 $tag_3$ 和 $tag_4$ 两个加法标记给清空。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll N=200200;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,q,op,l,r,v;
struct Node{
	ll l,r;
	ll sum;
	ll Max1,Max2;
	ll tag1,tag2;
	ll tag3,tag4;
}X[N<<2];
void pushup(ll k){
	X[k].sum=X[k<<1].sum+X[k<<1|1].sum;
	X[k].Max1=max(X[k<<1].Max1,X[k<<1|1].Max1);
	X[k].Max2=max(X[k<<1].Max2,X[k<<1|1].Max2);
}
void push_down(ll k){
	if(X[k].tag1!=-1){
		X[k<<1].tag3=X[k<<1|1].tag3=0;
		X[k<<1].tag1=X[k<<1|1].tag1=X[k].tag1;
		X[k<<1].Max1=X[k<<1|1].Max1=X[k].tag1;
		X[k].tag1=-1;
	}
	if(X[k].tag2!=-1){
		X[k<<1].tag4=X[k<<1|1].tag4=0;
		X[k<<1].tag2=X[k<<1|1].tag2=X[k].tag2;
		X[k<<1].Max2=X[k<<1|1].Max2=X[k].tag2;
		X[k].tag2=-1;
	}
	if(X[k].tag3){
		X[k<<1].tag3+=X[k].tag3;
		X[k<<1|1].tag3+=X[k].tag3;
		X[k<<1].Max1+=X[k].tag3;
		X[k<<1|1].Max1+=X[k].tag3;
		X[k].tag3=0;
	}
	if(X[k].tag4){
		X[k<<1].tag4+=X[k].tag4;
		X[k<<1|1].tag4+=X[k].tag4;
		X[k<<1].Max2+=X[k].tag4;
		X[k<<1|1].Max2+=X[k].tag4;
		X[k].tag4=0;		
	}
}
void build(ll k,ll l,ll r){
	X[k].l=l,X[k].r=r;
	X[k].tag1=X[k].tag2=-1;
	if(l==r){
		X[k].sum=1;
		return ;
	}
	ll mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
void updata1(ll k,ll l,ll r,ll v){
	if(r<l)
	  return ;
	if(X[k].l==l&&r==X[k].r){
		X[k].tag3=0;
		X[k].tag1=X[k].Max1=v;
		return ;
	}
	push_down(k);
	ll mid=(X[k].l+X[k].r)>>1;
	if(r<=mid)
	  updata1(k<<1,l,r,v);
	else if(l>mid)
	  updata1(k<<1|1,l,r,v);
	else{
		updata1(k<<1,l,mid,v);
		updata1(k<<1|1,mid+1,r,v);
	}
	pushup(k);
}
void updata2(ll k,ll l,ll r,ll v){
	if(r<l)
	  return ;
	if(X[k].l==l&&r==X[k].r){
		X[k].tag4=0;
		X[k].tag2=X[k].Max2=v;
		return ;
	}
	push_down(k);
	ll mid=(X[k].l+X[k].r)>>1;
	if(r<=mid)
	  updata2(k<<1,l,r,v);
	else if(l>mid)
	  updata2(k<<1|1,l,r,v);
	else{
		updata2(k<<1,l,mid,v);
		updata2(k<<1|1,mid+1,r,v);
	}
	pushup(k);
}
void updata3(ll k,ll l,ll r,ll v){
	if(r<l)
	  return ;
	if(X[k].l==l&&r==X[k].r){
		X[k].tag3+=v; 
		X[k].Max1+=v;
		return ;
	}
	push_down(k);
	ll mid=(X[k].l+X[k].r)>>1;
	if(r<=mid)
	  updata3(k<<1,l,r,v);
	else if(l>mid)
	  updata3(k<<1|1,l,r,v);
	else{
		updata3(k<<1,l,mid,v);
		updata3(k<<1|1,mid+1,r,v);
	}
	pushup(k);
}
void updata4(ll k,ll l,ll r,ll v){
	if(r<l)
	  return ;
	if(X[k].l==l&&r==X[k].r){
		X[k].tag4+=v; 
		X[k].Max2+=v;
		return ;
	}
	push_down(k);
	ll mid=(X[k].l+X[k].r)>>1;
	if(r<=mid)
	  updata4(k<<1,l,r,v);
	else if(l>mid)
	  updata4(k<<1|1,l,r,v);
	else{
		updata4(k<<1,l,mid,v);
		updata4(k<<1|1,mid+1,r,v);
	}
	pushup(k);
}
void Find(ll k,ll l,ll r,ll v){
	if(max(X[k].Max1,X[k].Max2)<v||!X[k].sum)
	  return ;
	if(X[k].l==X[k].r){
		X[k].sum=0;
		return ;
	}
	push_down(k);
	ll mid=(X[k].l+X[k].r)>>1;
	if(r<=mid)
	  Find(k<<1,l,r,v);
	else if(l>mid)
	  Find(k<<1|1,l,r,v);
	else{
		Find(k<<1,l,mid,v);
		Find(k<<1|1,mid+1,r,v);
	}
	pushup(k);
}
int main(){
//	freopen("A.in","r",stdin);
	n=read(),q=read();
	build(1,1,n);
	while(q--){
		op=read();
		if(op==1){
			l=read(),r=read(),v=read();
			updata2(1,l,r,0);
			updata1(1,1,l-1,0);
			updata1(1,r+1,n,0);
			updata3(1,l,r,v);
			updata4(1,1,l-1,v);
			updata4(1,r+1,n,v);
		}
		else if(op==2){
			l=read(),r=read(),v=read();
			Find(1,l,r,v);
		}
		else{
			write(X[1].sum);
			putchar('\n');
		}
	}
	return 0;
}