XOR的艺术

tr[p]除了表示区间p中1的和，也表示区间p中1的个数
懒标记ly[p]表示其左右儿子区间（tr[p* 2] 和 tr[p*2+1] ）的待操作次数
tr[p]的待操作次数是ly[p/2]
当add到p时，tr[p]一定要更新（记住）
懒标记是线段树的灵魂，没有懒标记，线段树比朴素修改还要慢

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=2e5+7;
ll tr[N<<2],ly[N<<2],a[N];
void bulid(int p,int l,int r){
    if(l==r){
        tr[p]=a[l];return ;
    }
    int mid=(l+r) >> 1;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    tr[p]=tr[p*2]+tr[p*2+1];
}
void pushdown(int p,int len){
    if(ly[p]%2){
        ly[p*2]++;ly[p*2]%=2;
        tr[p*2]=len-len/2-tr[p*2];
        ly[p*2+1]++;ly[p*2+1]%=2;
        tr[p*2+1]=len/2-tr[p*2+1];
    }
    ly[p]=0;
}
void add(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        ly[p]++;ly[p]%=2;
        tr[p]=r-l+1-tr[p];
        return ;
    }
    pushdown(p,r-l+1);
    int mid=(l+r)>>1;
    if(x<=mid) add(p*2,l,mid,x,y);
    if(mid+1<=y) add(p*2+1,mid+1,r,x,y);
    tr[p]=tr[p*2]+tr[p*2+1];
}
ll ask(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return tr[p];
    }
    pushdown(p,r-l+1);
    int mid=(l+r)>>1;
    ll res=0;
    if(x<=mid) res+=ask(p*2,l,mid,x,y);
    if(mid+1<=y) res+=ask(p*2+1,mid+1,r,x,y);
    return res;
}
int n,m;
int main(){
    cin >> n >> m;
    string str;
    cin >> str;
    for(int i=0;i<str.size();++i){
        a[i+1]=str[i]-'0';
    }
    bulid(1,1,n);
    int op,x,y;
    while(m--){
        cin >> op >> x >> y;
        if(op==0) add(1,1,n,x,y);
        else cout << ask(1,1,n,x,y) << "\n";
    }
    return 0;
}