这道题好像需要用到线段树喵！

如果不会的话先听小科普：

线段树是一棵二叉树，每个节点代表一个区间[l, r]。如果这个区间还能划分（即l < r），那么它就有左右两个孩子，分别代表区间[l, mid]和[mid+1, r]，其中mid = (l + r) / 2。

由于是二叉树的缘故，若它的下标为n，那么它的左右孩子的下标分别等于2*n和2*n+1喵~

（用爪子轻轻拍拍代码）你看，我们有一个好~~长的街道，街上每个房子都住着一只猫猫，有的在睡觉（0），有的在玩毛线球（1）。我们猫猫巡逻队要管理整条街呢！喵~

猫猫巡逻队的组织结构（node）

struct node
{
    int l, r;      // 本队猫猫负责的街道范围
    int sum;       // 这个范围里有多少只在玩毛线球的猫猫
    int lazy = 0;     // 小本本上记的之前偷了几次懒
};
  • 每个队长都有管理范围
  • 队长不用亲自数猫，问在自己范围内队长就行了喵~

建立巡逻队（build函数）

（舔毛）一开始，猫猫们要排好队伍喵！

void build(...) {
    tree[rt].l = l;  // 本队长负责从l号房
    tree[rt].r = r;  // 到r号房喵！
    if(l == r) {     // 如果只管一个房子
        tree[rt].sum = data[l];  // 记下这只猫在玩球还是睡觉
        return;
    }
    int mid = (l + r) / 2;
    build(data, tree, 2*rt, l, mid);
    build(data, tree, 2*rt+1, mid+1, r);
    // 把地盘分给两个副队长去管~
    tree[rt].sum = tree[2*rt].sum + tree[2*rt+1].sum;
    // 然后本队长只要记住：玩球的猫总数 = 左队的 + 右队的
}

（如果不懂懒标记可以先去结算偷懒那里弄清楚懒标记是什么意思）

要变天了喵！（反转flip）

（眼睛眯成一条缝）天黑啦，主人说要把第l到第r房的猫猫状态都变一变！

void flip(...) {
    if(fl <= l && fr >= r) {  // 如果任务完全在我的管辖范围内
        // 玩球的猫猫数 = 总猫数 - 现在玩球的猫数
        tree[rt].sum = (r-l+1) - tree[rt].sum;
        // 因为玩球的会去睡觉，睡觉的会来玩球喵！
        tree[rt].lazy ^= 1;  // 在小本本上记一笔“这次先偷懒，问我的时候再变化”
                //因为偷两次懒等于没有偷懒
        return;  // 记完就去睡回笼觉啦~ zZZ
    }
    
    pushDown(rt);  // 先看看小本本有没有欠其他猫的任务
    
    if(fl <= mid) flip(tree, 2*rt, l, mid, fl, fr);
    if(fr > mid) flip(tree, 2*rt+1, mid+1, r, fl, fr);
    // 让左副队长和右副队长去执行各自的部分
    tree[rt].sum = tree[2*rt].sum + tree[2*rt+1].sum;
    // 最后更新本队长的记录
}

 检查小本本（pushDown函数）（清算偷懒）

（竖起耳朵，认真状）当需要深入查看时，就要处理小本本了喵：

void pushDown(int rt) {
    if(tree[rt].lazy == 1) {  // 哎呀，小本本上有待办事项！
        // 通知左副队长：“你管的区域要反转啦！”
        tree[left].sum = (它的辖区大小) - tree[left].sum;
        tree[left].lazy ^= 1;  // 让它也记在小本本上
        // 通知右副队长同样的事~
        (略)
        tree[rt].lazy = 0;  // 擦掉本子上的记录，任务下派啦！
    }
}

效率高的原因

（得意地摇尾巴）普通的笨方法是一只只猫去查看和改变，要跑好多路喵！但是我们猫猫巡逻队超聪明：

1，任务来了，只通知到刚好能全权负责的最小队长

2，队长在小本本上记一笔就不管了，继续打盹

3，只有真的需要详细了解时，才把任务下派

（懒惰标记作用）

（蹭蹭你的手）这样处理n=50万，q=50万的大数据时，我们的方法比笨方法快了几万倍呢！喵呜~

（用爪子画示意图）其实就是：

    线段树 = 猫猫们的层级管理体系

    懒标记 = 队长们偷懒用的小本本

    按需下传 = 真的需要时才去跑腿

（开心地转圈）这样既能快速回答主人的问题，又能高效执行任务，还有更多时间睡懒觉！完美喵~ ♪(^∇^*)

   如果还有不理解的地方看猫猫的代码一步一步推就可以了喵！

   好长的题解，猫猫燃尽了喵~

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

struct node
{
    int l,r;//该结点的左坐标和右坐标
    int sum,lazy=0;//[l,r]范围内1的个数和懒标记
};

void build(const vector<int> &data,vector<node> &tree,int rt,int l,int r)
{
    tree[rt].l=l;
    tree[rt].r=r;
    //初始化结点的左右端点坐标
    if(l==r)
    {
        tree[rt].sum=data[l];
        return;
    }
    int mid=(l+r)/2;
    build(data,tree,2*rt,l,mid);//递归构建左孩子
    build(data,tree,2*rt+1,mid+1,r);//递归构建右孩子
    tree[rt].sum=tree[2*rt].sum+tree[2*rt+1].sum;
    //1的数量为左右孩子（即两个互补子集）数量之和
}

void pushDown(vector<node> &tree,int rt)//更新懒标记并下派懒标记
{
    if(tree[rt].lazy==1)
    {
        int left=2*rt,right=2*rt+1;
        //更新左孩子
        tree[left].sum=(tree[left].r-tree[left].l+1)-tree[left].sum;
        tree[left].lazy^=1;
        //更新右孩子
        tree[right].sum=(tree[right].r-tree[right].l+1)-tree[right].sum;
        tree[right].lazy^=1;
        //清空当前标记
        tree[rt].lazy=0;
    }
}

int query(vector<node> &tree,int rt,int l,int r,int ql,int qr)
//ql,qr是查询区间的左右边界;查询[ql,qr]之间1的数量
{
    if(ql<=l&&qr>=r)//如果左右端被包括其中
    {
        return tree[rt].sum;//直接返回值
    }
    pushDown(tree,rt);//更新懒标记
    int mid=(l+r)/2;
    int res=0;
    //查询左端必须小于等于mid才有向左查询的必要，右端同理
    if(ql<=mid) res+=query(tree,2*rt,l,mid,ql,qr);
    if(qr>=mid+1) res+=query(tree,2*rt+1,mid+1,r,ql,qr);
    return res;
}

void flip(vector<node> &tree,int rt,int l,int r,int fl,int fr)
//fl,fr是反转区间的左右边界;反转[ql,qr]区间
{
    if(fl<=l&&fr>=r)//如果左右端被包括其中
    {
        tree[rt].sum=(r-l+1)-tree[rt].sum;
        //反转后1的总数一定等于区间长度减去反转前1的总数
        tree[rt].lazy^=1;
        //向下做懒惰标记
        return;
    }
    pushDown(tree,rt);
    int mid=(l+r)/2;
    if(fl<=mid) flip(tree,2*rt,l,mid,fl,fr);
    if(fr>mid) flip(tree,2*rt+1,mid+1,r,fl,fr);
    tree[rt].sum=tree[2*rt].sum+tree[2*rt+1].sum;
}

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

    int n,q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> data(n+1);//储存01串
    for(int i=0;i<s.size();i++)
    {
        data[i+1]=s[i]-'0';
    }
    //初始化
    vector<node> tree(4*n+5);//线段树范围差不多是01串的4倍
    build(data,tree,1,1,n);//构建线段树
    while(q--)
    {
        int op,l,r;cin >> op >> l >> r;
        if(op==1) flip(tree,1,1,n,l,r);//反转
        else if(op==2) cout << query(tree,1,1,n,l,r) <<'\n';//数一
    }
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/