线段树 维护三个变量 1.c0:区间变成0所需的修改次数

2.c1:区间变成1所需的修改次数。

3.lazy:懒惰标记，记录是否需要翻转区间。

如果反转就下传标记，然后交换c0和c1 最后输出的是min(c0,c1) 时间复杂度O（n log n)

#include <bits/stdc++.h>
using namespace std;
const int N = 300010; 
char s[N];
int n, q; 
struct Node {
    int l, r;
    int c0, c1;
    int lazy;
    int len;
} tr[N << 2]; 
struct tree {
    int c0, c1, len;
}; 
#define ls (u<<1)
#define rs (u<<1|1) 
tree merge(tree a, tree b) {
    if (a.len == 0) return b;
    if (b.len == 0) return a;
    tree res;
    if (a.len & 1) {
        res.c0 = a.c0 + b.c1;
        res.c1 = a.c1 + b.c0;
    } else {
        res.c0 = a.c0 + b.c0;
        res.c1 = a.c1 + b.c1;
    }
    res.len = a.len + b.len;
    return res;
} 
void update(int u) {
    tr[u].len = tr[ls].len + tr[rs].len;
    if (tr[ls].len & 1) {
        tr[u].c0 = tr[ls].c0 + tr[rs].c1;
        tr[u].c1 = tr[ls].c1 + tr[rs].c0;
    } else {
        tr[u].c0 = tr[ls].c0 + tr[rs].c0;
        tr[u].c1 = tr[ls].c1 + tr[rs].c1;
    }
} 
void pushdown(int u) {
    if (tr[u].lazy) {
        tr[u].lazy = 0;
        if (tr[ls].len) {
            tr[ls].lazy ^= 1;
            swap(tr[ls].c0, tr[ls].c1);
        }
        if (tr[rs].len) {
            tr[rs].lazy ^= 1;
            swap(tr[rs].c0, tr[rs].c1);
        }
    }
}  
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    tr[u].lazy = 0;
    tr[u].len = r - l + 1;
    if (l == r) {
        if (s[l] == '0') {
            tr[u].c0 = 0;
            tr[u].c1 = 1;
        } else {
            tr[u].c0 = 1;
            tr[u].c1 = 0;
        }
        return;
    } 
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    update(u);
}

void modify(int u, int L, int R) {
    if (L <= tr[u].l && tr[u].r <= R) {
        tr[u].lazy ^= 1;
        swap(tr[u].c0, tr[u].c1);
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (L <= mid) modify(ls, L, R);
    if (R > mid) modify(rs, L, R);
    update(u);
} 
tree query(int u, int L, int R) {
    if (L <= tr[u].l && tr[u].r <= R) {
        return { tr[u].c0, tr[u].c1, tr[u].len };
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    tree res = {0, 0, 0};
    if (L <= mid) {
        res = query(ls, L, R);
    }
    if (R > mid) {
        if (res.len == 0) {
            res = query(rs, L, R);
        } else {
            tree tmp = query(rs, L, R);
            res = merge(res, tmp);
        }
    }
    return res; 
} 
int main() {
    scanf("%d%d", &n, &q);
    scanf("%s", s + 1);
    build(1, 1, n);
    while (q--) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1) {
            modify(1, l, r);
        } else {
            tree res = query(1, l, r);
            printf("%d\n", min(res.c0, res.c1));
        }
    }
    return 0;
}