蒟蒻求助,不知道为何会WA
查看原帖
蒟蒻求助,不知道为何会WA
152505
沙鵖之祖楼主2021/11/18 18:38
后来用题解区的方法A了这道题,但不知道为何原来的写法会WA/kk:
#include<bits/stdc++.h>
#define ll long long
#define g getchar()
#define pc(a) putchar(a)
using namespace std;

//别介意这些开头的鬼定义

const ll N=2e6+7,maxn=1e18+7;
ll lef[N],rig[N],num[N],tre[N],
	l[N],r[N],n,tot,op[N],tag[N];
 //提前用lef,rig两个数组维护了区间边界
 //tre数组维护区间状态:0代表全没选,1表示全被选,2代表有的选了有的没选
 //tag维护懒标记:0表示无标记,1表示1操作,2表示2操作,3表示3操作
 //你没看错,源代码既没两个tag,也没有维护区间和,但我认为也可以,但显然问题就出现在这上面
 
	
inline ll rd(){
	ll x=0,s=1;
	char c=g;
	while(c>'9'||c<'0'){
		if(c=='-') s=-1;c=g;
	}while(c<='9'&&c>='0')
		x=x*10+c-'0',c=g;
	return s*x;
}void qp(ll u){
	if(u<0) pc('-'),u=-u;
	if(u/10==0){
		pc(u+'0');return;
	}qp(u/10);
	pc(u%10+'0');
}

inline bool cmp(ll x,ll y){
	return x<y;
}

inline void build(ll l,ll r,ll u){
	tag[u]=2;
	if(r==l){
		lef[u]=num[l];
		rig[u]=num[l];
		return;
	}ll mid=(l+r)>>1;
	build(l,mid,u*2);
	build(mid+1,r,u*2+1);
	lef[u]=num[l];
	rig[u]=num[r];
}

inline void clr(ll u){
	if(tag[u]==3){
		tag[u]=0;return;
	}if(tag[u]==1){
		tag[u]=2;tre[u]=0;return;	
	}if(tag[u]==2){
		tag[u]=1;tre[u]=1;return;
	}tag[u]=3;
}inline void pushdown(ll u){
	if(tag[u]==1){
		tag[u*2]=tag[u*2+1]=1;
		tre[u*2]=tre[u*2+1]=1;
	}else if(tag[u]==2){
		tag[u*2]=tag[u*2+1]=2;
		tre[u*2]=tre[u*2+1]=0;
	}else if(tag[u]==3){
		clr(u*2);clr(u*2+1);
	}tag[u]=0;
}

//修改操作
inline void chg(ll t,ll u,ll l,ll r){
	if(rig[u]<l||lef[u]>r) return;
	if(lef[u]>=l&&rig[u]<=r){
		if(t==1){
			tre[u]=1;tag[u]=1;return;	
		}else if(t==2){
			tre[u]=0;tag[u]=2;return;
		}else{
			clr(u);return;
		}
	}pushdown(u);
	chg(t,u*2,l,r);
	chg(t,u*2+1,l,r);
	tre[u]=(tre[u*2]==tre[u*2+1]? 
		tre[u*2]:2);
}

inline ll find(ll u){
	if(tre[u]==1) return maxn;
	if(lef[u]==rig[u]) return lef[u];
	pushdown(u);
	ll f=find(u*2);
	if(f==maxn) 
		return find(u*2+1);
	else return f;
}

int main(){
	n=rd();
	for(ll i=1;i<=n;i++){
		op[i]=rd(),l[i]=rd(),r[i]=rd();
		num[++tot]=l[i],num[++tot]=r[i]; 
		num[++tot]=r[i]+1;
	}num[++tot]=1;num[++tot]=maxn;
	sort(num+1,num+tot+1,cmp);
	tot=unique(num+1,num+1+tot)-(num+1);	
	build(1,tot,1);
	for(ll i=1;i<=n;i++){
		chg(op[i],1,l[i],r[i]);
		qp(find(1));pc('\n');
	}return 0;
}

2021/11/18 18:38
加载中...