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

一个简单的线段树

#include <bits/stdc++.h>
#define il inline
#define double long double
using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128 = __int128_t;

const ll N = 5e5 + 5, mod = 1e9+7, inf = 2e18;
const double eps = 1e-9;
double PI = 3.1415926;

int a[N],tree[N<<2],tag[N<<2];

il int lson(int i){
    return i<<1;
}
il int rson(int i){
    return i<<1|1;
}
il void up(int i){
    tree[i]=tree[lson(i)]+tree[rson(i)];
}

il void build(int i,int pl,int pr){
    if(pl==pr){
        tree[i]=a[pl];
        return ;
    }
    int mid=pl+pr>>1;
    build(lson(i),pl,mid);
    build(rson(i),mid+1,pr);

    up(i);
}

il void laze(int i,int l,int r,int v){
    tag[i]^=v;
    tree[i]=(r-l+1)-tree[i];
}
il void down(int i,int pl,int pr){
    if(tag[i]){
        int mid=pl+pr>>1;
        laze(lson(i),pl,mid,tag[i]);
        laze(rson(i),mid+1,pr,tag[i]);
        tag[i]=0;
    }
}
il void updata(int i,int pl,int pr,int L,int R){
    if(L<=pl&&pr<=R){
        laze(i,pl,pr,1);
        return ;
    }
    down(i,pl,pr);
    int mid=pl+pr>>1;
    if(L<=mid){
        updata(lson(i),pl,mid,L,R);
    }
    if(R>mid){
        updata(rson(i),mid+1,pr,L,R);
    }
    up(i);
}

il int query(int i,int pl,int pr,int L,int R){
    if(L<=pl&&pr<=R){
        return tree[i];
    }
    down(i,pl,pr);
    int mid=pl+pr>>1;
    int ans=0;
    if(L<=mid){
        ans+=query(lson(i),pl,mid,L,R);
    }
    if(R>mid){
        ans+=query(rson(i),mid+1,pr,L,R);
    }
    return ans;
}

il void solve(){
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    for(int i=1;i<=n;i++){
        a[i]=s[i-1]-'0';
    }
    build(1,1,n);
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){
            updata(1,1,n,l,r);
        }else{
            cout<<query(1,1,n,l,r)<<'\n';
        }
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    // cin >> t;

    while (t--){

        solve();
    }

    return 0;
}