线段树这么解是正确的吗
查看原帖
线段树这么解是正确的吗
261262
WaltVBAlston楼主2021/9/9 17:06

RT,怀疑人生了,感觉没写错哪里啊,但是样例都过不去

#include<iostream>
using namespace std;
#define MAXN 200005
struct node{
	int l,r,num1,num0,tag;
}tree[4*MAXN];
int n,m,a[MAXN];
char c;
void pushdown(int i){
	tree[i].tag=tree[i].tag%2;
	if(tree[i].tag==1){
		tree[i*2].tag++;
		tree[i*2+1].tag++;
		int t=tree[i*2].num0;
		tree[i*2].num1=tree[i*2].num0;
		tree[i*2].num0=t;
		t=tree[i*2+1].num0;
		tree[i*2+1].num1=tree[i*2+1].num0;
		tree[i*2+1].num0=t;
		tree[i].tag=0;
	}
	return;
}
void update(int i,int l,int r){
	if(tree[i].l>=l&&tree[i].r<=r){
		tree[i].tag++;
		int t=tree[i].num0;
		tree[i].num1=tree[i].num0;
		tree[i].num0=t;
		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].num0=tree[i*2].num0+tree[i*2+1].num0;
	tree[i].num1=tree[i*2].num1+tree[i*2+1].num1;
	return;
}
int sum(int i,int l,int r){
	if(tree[i].l>=l&&tree[i].r<=r)
		return tree[i].num1;
	pushdown(i);
	int mid=(tree[i].l+tree[i].r)/2,res=0;
	if(mid>=l)
		res+=sum(i*2,l,r);
	if(mid+1<=r)
		res+=sum(i*2+1,l,r);
	return res;
}
void build(int i,int l,int r){
	tree[i].l=l,tree[i].r=r;
	if(l==r){
		tree[i].num0=tree[i].num1=0;
		if(a[l]==0)
			tree[i].num0++;
		else
			tree[i].num1++;
		return;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	tree[i].num0=tree[i*2].num0+tree[i*2+1].num0;
	tree[i].num1=tree[i*2].num1+tree[i*2+1].num1;
	return;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>c;
		a[i]=c-'0';
	}
	build(1,1,n);
	while(m--){
		int op,l,r;
		cin>>op>>l>>r;
		if(op==0)
			update(1,l,r);
		else
			cout<<sum(1,l,r)<<endl;
	}
	return 0;
}
2021/9/9 17:06
加载中...