萌新求助超简单线段树QAQ
查看原帖
萌新求助超简单线段树QAQ
261262
WaltVBAlston楼主2021/10/3 08:55

RT,自认为写的没有问题了,但是就是样例输出错误,求助!

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