洛谷 P2574 XOR的艺术（线段树）

 

 

const int N=2e5+5;

    int i,j,k;
    int n,m;
    int a[N];  
    struct Node
    {
        int l,r;
        int lazy;
        int sum;
        void update()
        {
            lazy^=1;
            sum=(r-l+1)-sum;
        }
    }t[N<<2];

void push_up(int id)
{
    t[id].sum=t[id<<1].sum+t[id<<1|1].sum;
}

void push_down(int id)
{
    int x=t[id].lazy;
    if(x){
        t[id<<1].update();
        t[id<<1|1].update();
        t[id].lazy=0;
    }
}

void build(int l,int r,int id)
{
    t[id].l=l,t[id].r=r;
    t[id].lazy=0;
    if(l==r) t[id].sum=a[l];
    else{
        int mid=l+r>>1;
        build(l,mid,id<<1);
        build(mid+1,r,id<<1|1);
        push_up(id);
    }
}

void update(int l,int r,int id)
{
    int L=t[id].l,R=t[id].r;
    if(L>=l && r>=R) t[id].update();
    else{
        int mid=L+R>>1;
        push_down(id);
        if(mid>=l) update(l,r,id<<1);
        if(r>=mid+1) update(l,r,id<<1|1);
        push_up(id);
    }
}

int query(int l,int r,int id)
{
    int L=t[id].l,R=t[id].r;
    if(L>=l && r>=R) return t[id].sum;
    else{
        int mid=L+R>>1;
        push_down(id);
        int ans=0;
        if(mid>=l) ans+=query(l,r,id<<1);
        if(r>=mid+1) ans+=query(l,r,id<<1|1);
        push_up(id);
        return ans;
    }
}

int main()
{
    //IOS;
    while(~sdd(n,m)){
        for(int i=1;i<=n;i++) scanf("%1d",&a[i]);
        build(1,n,1);
        int ans;
        while(m--){
            int opt=read(),l=read(),r=read();
            if(opt) pd(query(l,r,1));
            else update(l,r,1);
        }
    }
    //PAUSE;
    return 0;
}