RT,用的线段树,可能因为不是很熟吧,好多个bug,调完之后还是过不了样例,求助!
#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;
}
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;
}