# analysis

First of all, it is not hard to see that this is a line tree problem. Then, because the operation to be maintained by this problem is different from that of the general line tree, it is considered to modify the pushdown function and lazy flag

Consider modifying the function. If you invert each number in the interval, the number of 1 = the number of interval elements - the number of original interval 1.

At this time, it's easy to think that the lazy flag represents the XOR of this interval, 1 represents XOR, 0 represents not XOR
Since A^ 1 ^1=A, if an interval is XOR twice, it is equivalent to not being XOR, that is to say, the lazy flag should also meet the XOR principle

Since then, the idea has been basically completed

# code

```#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
int n,m;
const int maxn=200010;
int sum[maxn<<2],lazy[maxn<<2];
int a[maxn];
char _A[maxn];
x=0;char r=getchar();T neg=1;
while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();}
x*=neg;
}
inline void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
inline void pushdown(int rt,int l,int r){
if(!lazy[rt])return;
int mid=(l+r)>>1;
lazy[rt<<1]^=1;
lazy[rt<<1|1]^=1;
sum[rt<<1]=mid-l+1-sum[rt<<1];
sum[rt<<1|1]=r-(mid+1)+1-sum[rt<<1|1];
lazy[rt]=0;
}
void buildtree(int l,int r,int rt){
if(l==r){
sum[rt]=a[l];
return;
}
int mid=((l+r)>>1);
buildtree(l,mid,rt<<1);
buildtree(mid+1,r,rt<<1|1);
pushup(rt);
}
int query(int l,int r,int nl,int nr,int rt){
if(l<=nl&&nr<=r)return sum[rt];
pushdown(rt,nl,nr);
int mid=((nl+nr)>>1);
int _sum=0;
if(mid>=l)_sum+=query(l,r,nl,mid,rt<<1);
if(mid<r)_sum+=query(l,r,mid+1,nr,rt<<1|1);
return _sum;
}
void update(int l,int r,int nl,int nr,int rt){
if(l<=nl&&nr<=r){
lazy[rt]^=1;
sum[rt]=(nr-nl+1)-sum[rt];
return;
}
pushdown(rt,nl,nr);
int mid=((nl+nr)>>1);
if(mid>=l)update(l,r,nl,mid,rt<<1);
if(mid<r)update(l,r,mid+1,nr,rt<<1|1);
pushup(rt);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("datain.txt","r",stdin);
#endif // ONLINE_JUDGE
clean(sum,0),clean(lazy,0);
scanf("%s",_A);
loop(i,1,n)a[i]=_A[i-1]-'0';
buildtree(1,n,1);
loop(i,1,m){
if(_p==0)update(_l,_r,1,n,1);
else if(_p==1)printf("%d\n",query(_l,_r,1,n,1));
}
return 0;
}

```

# anayisis

That's the question above! No need to change the code

# code

```#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
int n,m;
const int maxn=200010;
int sum[maxn<<2],lazy[maxn<<2];
int a[maxn];
char _A[maxn];
x=0;char r=getchar();T neg=1;
while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();}
x*=neg;
}
inline void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
inline void pushdown(int rt,int l,int r){
if(!lazy[rt])return;
int mid=(l+r)>>1;
lazy[rt<<1]^=1;
lazy[rt<<1|1]^=1;
sum[rt<<1]=mid-l+1-sum[rt<<1];
sum[rt<<1|1]=r-(mid+1)+1-sum[rt<<1|1];
lazy[rt]=0;
}
void buildtree(int l,int r,int rt){
if(l==r){
sum[rt]=a[l];
return;
}
int mid=((l+r)>>1);
buildtree(l,mid,rt<<1);
buildtree(mid+1,r,rt<<1|1);
pushup(rt);
}
int query(int l,int r,int nl,int nr,int rt){
if(l<=nl&&nr<=r)return sum[rt];
pushdown(rt,nl,nr);
int mid=((nl+nr)>>1);
int _sum=0;
if(mid>=l)_sum+=query(l,r,nl,mid,rt<<1);
if(mid<r)_sum+=query(l,r,mid+1,nr,rt<<1|1);
return _sum;
}
void update(int l,int r,int nl,int nr,int rt){
if(l<=nl&&nr<=r){
lazy[rt]^=1;
sum[rt]=(nr-nl+1)-sum[rt];
return;
}
pushdown(rt,nl,nr);
int mid=((nl+nr)>>1);
if(mid>=l)update(l,r,nl,mid,rt<<1);
if(mid<r)update(l,r,mid+1,nr,rt<<1|1);
pushup(rt);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("datain.txt","r",stdin);
#endif // ONLINE_JUDGE
clean(sum,0),clean(lazy,0);