0分求助
查看原帖
0分求助
793625
Pink_Cut_Tree楼主2023/12/20 22:09

感觉没啥问题啊

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
#define ls(x) x*2
#define rs(x) x*2+1
int n,m,l,r;
char c[N];
bool a[N],op; 
int w[4*N],lzy[4*N];
void pushup(int u){
	w[u]=w[ls(u)]+w[rs(u)];
} 
void build(int u,int l,int r){
	if(l==r){
		w[u]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(ls(u),l,mid);
	build(rs(u),mid+1,r);
	pushup(u);
}
void pushdown(int u,int len){
	if(lzy[u]){
		w[ls(u)]=len-w[ls(u)];
		w[rs(u)]=len-w[rs(u)];
		lzy[ls(u)]^=1;
		lzy[rs(u)]^=1;
		lzy[u]=0;
	}
}
void modify(int u,int l,int r,int L,int R){
	if(l<=L&&R<=r){
		w[u]=r-l+1-w[u];
		lzy[u]^=1;
	}
	else if(!(l>R||r<L)){
		pushdown(u,r-l+1);
		int mid=(l+r)/2;
		modify(ls(u),l,mid,L,R);
		modify(rs(u),mid+1,r,L,R);
		pushup(u);
	}
}
int qry(int u,int l,int r,int L,int R){
	if(l<=L&&R<=r){
		return w[u];
	}
	else if(!(l>R||r<L)){
		pushdown(u,r-l+1);
		int mid=(l+r)/2;
		return qry(ls(u),l,mid,L,R)+qry(rs(u),mid+1,r,L,R);
	}
return 0;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>c[i];
		a[i]=c[i]-'0';
	}
	build(1,1,n);
	while(m--){
		cin>>op>>l>>r;
		if(op){
			cout<<qry(1,1,n,l,r)<<"\n";
		}
		else{
			modify(1,1,n,l,r);
		}
	}
return 0;
}
2023/12/20 22:09
加载中...