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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6+10;
int a[N];
int sum[N];
bool chg[N];
void up(int i)
{
    sum[i] = sum[i<<1]+sum[i<<1|1];
}

void lazy(int i,int n)
{
    sum[i] = n-sum[i];
    chg[i] ^=1;
}

void down(int i,int ln,int rn)
{
    if(chg[i])
    {
        lazy(i<<1,ln);
        lazy(i<<1|1,rn);
        chg[i] = false;
    }
}

void upd(int jobl,int jobr,int l,int r,int i)
{
    if(jobl<=l&&jobr>=r)
    {
        lazy(i,r-l+1);
        return ;
    }
    else 
    {
        int mid = (l+r)>>1;
        int ans = 0;
        down(i,mid-l+1,r-mid);
        if(jobl<=mid)
        {
            upd(jobl,jobr,l,mid,i<<1);
        }
        if(jobr>mid) 
        {
            upd(jobl,jobr,mid+1,r,i<<1|1);
        }      
        up(i);      
    }

}

int query(int jobl,int jobr,int l,int r,int i)
{
    if(jobl<=l&&jobr>=r)
    {
        return sum[i];
    }
    else 
    {
        int mid = (l+r)>>1;
        int ans = 0;
        down(i,mid-l+1,r-mid);
        if(jobl<=mid)
        {
            ans += query(jobl,jobr,l,mid,i<<1);
        }
        if(jobr>mid) 
        {
            ans += query(jobl,jobr,mid+1,r,i<<1|1);
        }
        up(i);
        return ans;
    }

}

void build(int l,int r,int i)
{
    if(l==r)
    {
        sum[i] = a[l];
    }
    else 
    {
        int mid = (l+r)>>1;
        build(l,mid,i<<1);
        build(mid+1,r,i<<1|1);
        up(i);
    }
    chg[i] = false;
}

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

线段树板子题