简单线段树求助,开关灯问题QAQ
查看原帖
简单线段树求助,开关灯问题QAQ
261262
WaltVBAlston楼主2021/10/3 14:14

现在有一个问题,样例的前三个操作似乎是正常的,但是不知道怎么弄完第四个操作就没有开的灯了。实在调不出来了,求助大佬!

#include<iostream>
#define MAXN 100005
using namespace std;
int n,m;
struct node{
	int l,r,on,tag,len;
}tree[4*MAXN];
void pushdown(int i){
	if(tree[i].tag%2!=0){
		tree[i*2].tag++,tree[i*2+1].tag++;
		tree[i*2].on=tree[i*2].len-tree[i*2].on;
		tree[i*2+1].on=tree[i*2+1].len-tree[i*2+1].on;
	}
	tree[i].tag=0;
	return;
}
void build(int i,int l,int r){
	tree[i].l=l,tree[i].r=r,tree[i].on=0,tree[i].tag=0,tree[i].len=r-l+1;
	if(l==r)
		return;
	int mid=(l+r)/2;
	build(i*2,l,mid),build(i*2+1,mid+1,r);
	return;
}
void update(int i,int l,int r){
	if(tree[i].l>=l&&tree[i].r<=r){
		tree[i].on=tree[i].len-tree[i].on;
		return;
	}
	pushdown(i);
	int mid=(tree[i].l+tree[i].r)/2;
	if(mid>=l)
		update(i*2,l,r);
	if(mid+1<=r)
		update(i*2+1,l,r);
	tree[i].on=tree[i*2].on+tree[i*2+1].on;
	return;
}
int find(int i,int l,int r){
	if(tree[i].l>=l&&tree[i].r<=r)
		return tree[i].on;
	pushdown(i);
	int mid=(tree[i].l+tree[i].r)/2,res=0;
	if(mid>=l)
		res+=find(i*2,l,r);
	if(mid+1<=r)
		res+=find(i*2+1,l,r);
	return res;
}
int main(){
	cin>>n>>m;
	build(1,1,n);
	cout<<tree[1].on<<endl; 
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==0)
			update(1,x,y);
		else
			cout<<find(1,x,y)<<endl;
		//cout<<endl<<tree[1].on<<" gengengen"<<endl<<endl;
	}
	return 0;
}
2021/10/3 14:14
加载中...