线段树10分求调
查看原帖
线段树10分求调
524091
dami826楼主2024/5/28 21:46
#include<bits/stdc++.h>
using namespace std;
long long n,m;
struct segment_tree{
	long long tree[400001];
	bool lazy[400001];
	inline void down(long long index,long long mid,long long left,long long right){
		if(!lazy[index]){
			return;
		}
		lazy[index<<1]=!(lazy[index<<1]);
		lazy[(index<<1)+1]=!(lazy[(index<<1)+1]);
		tree[index<<1]+=(mid-left+1)-tree[index<<1];
		tree[(index<<1)+1]+=(right-mid)-tree[(index<<1)+1];
		lazy[index]=0;
	}
	void update(long long gleft,long long gright,long long index,long long left,long long right){
		//printf("%lld %lld %lld %lld %lld %lld\n",gleft,gright,index,x,left,right);
		if(gleft<=left&&right<=gright){
			tree[index]=(right-left+1)-tree[index];
			lazy[index]=!(lazy[index]);
			return;
		}
		if(right<gleft||gright<left){
			return;
		}
		long long mid=(left+right)>>1;
		down(index,mid,left,right);
		update(gleft,gright,index<<1,left,mid);
		update(gleft,gright,(index<<1)+1,mid+1,right);
		tree[index]=tree[index<<1]+tree[(index<<1)+1];
	}
	long long search(long long gleft,long long gright,long long index,long long left,long long right){
		if(left>gright||right<gleft){
			return 0;
		}
		if(left>=gleft&&right<=gright){
			return tree[index];
		}
		else{
			long long mid=(left+right)>>1;
			down(index,mid,left,right);
			return search(gleft,gright,index<<1,left,mid)+search(gleft,gright,(index<<1)+1,mid+1,right);
		}
	}
}; 
segment_tree tr;
int main(){
	scanf("%lld %lld",&n,&m);
	for(long long i=1;i<=m;i++){
		long long type,gleft,gright;
		scanf("%lld %lld %lld",&type,&gleft,&gright);
		if(type==0){
			tr.update(gleft,gright,1,1,n); 
		}
		else{
			printf("%lld\n",tr.search(gleft,gright,1,1,n));
		}
	} 
	return 0;
}
2024/5/28 21:46
加载中...