百度202425

#include<bits/stdc++.h> 
using namespace std;
#define ls u<<1
#define rs u<<1|1
const int N = 3e5+7;
int a[N];
struct node{
    int l,r,tag,odd[2],even[2];
}tr[N<<3];
int ok;
void pushup(int u)
{
    tr[u].odd[0] = tr[ls].odd[0] + tr[rs].odd[0];
    tr[u].odd[1] = tr[ls].odd[1] + tr[rs].odd[1];
    tr[u].even[0] = tr[ls].even[0] + tr[rs].even[0];
    tr[u].even[1] = tr[ls].even[1] + tr[rs].even[1];
}
void sw(int u)
{
    swap(tr[u].odd[0],tr[u].odd[1]);
    swap(tr[u].even[0],tr[u].even[1]);
}
void pushdown(int u)
{
    if(tr[u].tag)
    {
        sw(ls);
        sw(rs);
        tr[u].tag = 0;
        tr[ls].tag ^= 1;
        tr[rs].tag ^= 1;
    }
}
void build(int u,int l,int r)
{
    tr[u].l = l, tr[u].r = r;
    if(l==r)
    {
        if(l%2)     
            tr[u].odd[a[l]]++;
        else  
            tr[u].even[a[l]]++;
        return;
    }
    int mid = l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(u);
}
array<int,4> query(int u,int l,int r)
{
    array<int,4> res  = {0,0,0,0};
    array<int,4> tmp1 = {0,0,0,0};
    array<int,4> tmp2 = {0,0,0,0};
    if(l<=tr[u].l&&tr[u].r<=r)
        return {tr[u].odd[0],tr[u].odd[1],tr[u].even[0],tr[u].even[1]};
    pushdown(u);
    int mid = tr[u].l+tr[u].r>>1;
    if(l<=mid)  tmp1 = query(ls,l,r);
    if(r>mid)   tmp2 = query(rs,l,r);
    for(int i=0;i<4;i++)
        res[i] += tmp1[i],
        res[i] += tmp2[i];
    return res;
}
void change(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        sw(u);
        tr[u].tag ^= 1;
        return;
    }
    pushdown(u);
    int mid = tr[u].l+tr[u].r>>1;
    if(l<=mid)  change(ls,l,r);
    if(r>mid)   change(rs,l,r);
    pushup(u);
    ok = 1;
}
signed main()
{
    int n,q;
    string s;
    cin>>n>>q>>s;
    for(int i=1;i<=n;i++)
        a[i] = s[i-1] == '1';
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int op, l, r;
        cin>>op>>l>>r;
        if(op==1)
            change(1,l,r);
        else 
        {
            auto res = query(1,l,r);
            cout<<min(res[0]+ res[3],res[1]+ res[2])<<"\n";
        }
    }
}