线段树求调
查看原帖
线段树求调
593427
CZB59楼主2023/10/4 14:09
using namespace std;
#define inf 999999
#define mid (L+R>>1)
int tree[inf*4],tag[inf*4],a[inf],cnt,ans;
int n;
bitset<inf> vis;
int ls(int p){
	return p<<1;
}
int rs(int p){
	return p<<1+1;
}
void pushdown(int p){
	if(!tag[p])
	return ;
	tag[ls(p)] = tag[rs(p)] = tag[p];
	tree[ls(p)] = tree[rs(p)] = tag[p], tag[p] = 0;
}
void update(int l,int r,int L,int R,int c,int p){
	if(l<=L&&R<=r){
		tag[p]=c;
		tree[p]=c;
		return ;
	}
	pushdown(p);
	if(l<=mid)
	update(l,r,L,mid,c,ls(p));
	if(r>mid)
	update(l,r,mid+1,R,c,rs(p));
	if(tree[ls(p)]==tree[rs(p)]){
		tree[p]=tree[ls(p)];
	}
	else{
		tree[p]=-1;
	}
}
void query(int l,int r,int L,int R,int p){
	if(l<=L&&r>=R){
		if(!tree[p])
		return ;
			if(tree[p]<0){
				pushdown(p);
				if(l<=mid)
				query(l,r,L,mid,ls(p));
				if(r>mid)
				query(l,r,mid+1,R,rs(p));
			}
			else{
				if(!vis[tree[p]]){
					ans--;cnt++;vis[tree[p]]=1;
				}
			}
		
		return ;
	}
	pushdown(p);
	if(l<=mid)query(l,r,L,mid,ls(p));
	if(r>mid) query(l,r,mid+1,R,rs(p));
}
int main(){
	int m,len;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		char t;
		cin>>t;
		if(t=='A'){
			cin>>x>>y;
			query(x,y,1,200000,1);
			cout<<cnt<<endl;cnt=0;
			update(x,y,1,200000,i,1);
			ans++;
		}
		if(t=='B')
		{
			cout<<ans<<endl;
		}
	}
	return 0;
}```
2023/10/4 14:09
加载中...