题解 | 区间取反与区间数一

线段树维护一下区间一的个数，取反就用区间长度减去一的个数就行了

struct seg{
    int l,r;
    int c1;
    int lz;
}tr[N<<2];
string a;
void pushup(int p){
    tr[p].c1=tr[p<<1].c1+tr[p<<1|1].c1;
}
void pushdown(int p){
    if(tr[p].lz){
        tr[p].lz^=1;
        tr[p<<1].c1=(tr[p<<1].r-tr[p<<1].l+1)-tr[p<<1].c1;
        tr[p<<1|1].c1=(tr[p<<1|1].r-tr[p<<1|1].l+1)-tr[p<<1|1].c1;
        tr[p<<1].lz^=1;
        tr[p<<1|1].lz^=1;
    }
}
void build(int p,int l,int r){
    tr[p].l=l;
    tr[p].r=r;
    if(l==r){
        tr[p].c1=(a[l-1]=='1');
        tr[p].lz=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void add(int p,int L,int R){
    if(tr[p].r<L||R<tr[p].l)return ;
    if(L<=tr[p].l&&tr[p].r<=R){
        tr[p].c1=(tr[p].r-tr[p].l+1)-tr[p].c1;
        tr[p].lz^=1;
        return ;
    }
    pushdown(p);
    add(p<<1,L,R);
    add(p<<1|1,L,R);
    pushup(p);
}
int query(int p,int L,int R){
    if(tr[p].r<L||R<tr[p].l)return 0;
    if(L<=tr[p].l&&tr[p].r<=R){
        return tr[p].c1;
    }
    pushdown(p);
    return query(p<<1,L,R)+query(p<<1|1,L,R);
}
void solve(){
    int n,q;
    cin>>n>>q;
    cin>>a;
    build(1,1,a.size());
    for(int i=1;i<=q;i++){
        int op;
        cin>>op;
        if(op==1){
            int l,r;
            cin>>l>>r;
            add(1,l,r);
        }else{
            int l,r;
            cin>>l>>r;
            cout<<query(1,l,r)<<'\n';
        }
    }
}