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

#include <iostream>
#include <vector>
using namespace std;
struct Node{
    int l=0;
    int r=0;
    int reverseTag=0;
    int OneCounts=0;
    Node()=default;
    void setLR(int toL,int toR){
        l=toL;
        r=toR;
    }
};
//定义树结构
vector<Node> tree;
//定义数据数组
vector<int> arr;
//定义向上更新数组
void push_up(int node){
    tree[node].OneCounts=tree[2*node].OneCounts+tree[2*node+1].OneCounts;
}
//构建线段树
void buildSegment(int node){
    int l=tree[node].l;
    int r=tree[node].r;
    if(l==r){
        tree[node].OneCounts=(arr[l]==1?1:0);
        return;
    }
    int mid=(l+r)/2;
    tree[2*node].setLR(l, mid);
    buildSegment(2*node);
    tree[2*node+1].setLR(mid+1, r);
    buildSegment(2*node+1);
    //更新父节点
    push_up(node);
}
//定义下推子节点操作
void push_down_operat(int child){
    int l=tree[child].l;
    int r=tree[child].r;
    int len=r-l+1;
    tree[child].OneCounts=len-tree[child].OneCounts;
    tree[child].reverseTag ^= 1;
}
//定义下推操作
void push_down(int node){
    if(tree[node].reverseTag==1){
        push_down_operat(2*node);
        push_down_operat(2*node+1);
        tree[node].reverseTag=0;
    }

}
//定义区间更新
void update(int node,int toL,int toR){
    int l=tree[node].l;
    int r=tree[node].r;
    if(l>=toL && r<=toR){
        int len=r-l+1;
        tree[node].OneCounts=len-tree[node].OneCounts;
        tree[node].reverseTag=(tree[node].reverseTag==1?0:1);
        return;
    }
    //定义下推操作
    push_down(node);
    //【1，8】，【1，4】、【5，8】
    //查询【2，6】
    if(toL<=tree[2*node].r){
        update(2*node, toL, toR);
    }
    if(toR>=tree[2*node+1].l){
        update(2*node+1, toL, toR);
    }
    push_up(node);
}
//定义查询操作
int query(int node,int toL,int toR){
    int l=tree[node].l;
    int r=tree[node].r;
    if(toL<=l && r<=toR){
        return tree[node].OneCounts;
    }
    push_down(node);
    int total=0;
    if(toL<=tree[2*node].r){
        total+=query(2*node, toL, toR);
    }
    if(toR>=tree[2*node+1].l){
        total+=query(2*node+1, toL, toR);
    }
    return total;
}
int main() {
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    arr.resize(n+1,0);
    int i=1;
    for(char c:s){
        arr[i]=c-'0';
        i++;
    }
    tree.resize(4*n+5);
    tree[1].setLR(1, n);
    buildSegment(1);
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){
            update(1, l, r);
        }else{
            cout<<query(1, l, r)<<endl;
        }
    }
    return 0;
}