线段树10pts求助
查看原帖
线段树10pts求助
285373
BlachSnake楼主2021/2/6 20:43
#include<iostream>
using namespace std;
struct Segment_Tree{
	struct Tree{
		int val,tag;
	}t[262144];
	void GetUp(int d){
		t[d].val=t[d<<1].val+t[d<<1|1].val;
	}
	void PushDown(int d,int b,int e){
		if(t[d].tag){
			int m=b+e>>1;
			t[d<<1].tag^=1;
			t[d<<1|1].tag^=1;
			t[d<<1].val=b-m+1-t[d<<1].val;
			t[d<<1|1].val=e-m-t[d<<1|1].val;
			t[d].tag=0;
		}
	}
	void Change(int l,int r,int b,int e,int d){
		if(l<=b&&e<=r){
			t[d].tag^=1;
			t[d].val=e-b+1-t[d].val;
			return;
		}
		PushDown(d,b,e);
		int m=b+e>>1;
		if(l<=m)Change(l,r,b,m,d<<1);
		if(m<r)Change(l,r,m+1,e,d<<1|1);
		GetUp(d);
	}
	int Query(int l,int r,int b,int e,int d){
		if(l<=b&&e<=r)return t[d].val;
		PushDown(d,b,e);
		int m=b+e>>1,s=0;
		if(l<=m)s=Query(l,r,b,m,d<<1);
		if(m<r)s+=Query(l,r,m+1,e,d<<1|1);
		return s;
	}
};
Segment_Tree QwQ;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m,c,a,b;
	cin>>n>>m;
	while(m--){
		cin>>c>>a>>b;
		if(c)cout<<QwQ.Query(a,b,1,n,1)<<endl;
		else QwQ.Change(a,b,1,n,1);
	}
	return 0;
}

RT

2021/2/6 20:43
加载中...