洛谷——P2574 XOR的艺术

P2574 XOR的艺术

很久之前就想挑战一下这道题了，线段树下传标记的入门题，跟区间加法下传标记类似。

#include<bits/stdc++.h>

#define N 1000005

#define LL long long

#define RE register

#define IN inline

using namespace std;

IN void in(int &x){

    int flg=;RE char ch=getchar();x=;

    for(;ch>''||ch<'';){if(ch=='-') flg=-;ch=getchar();}

    for(;ch<=''&&ch>='';ch=getchar()) x=x*+ch-'';

    x*=flg;

}

struct node{

    int l,r,w,f;

}tr[N];

int n,m,ans,X,tot;

int e[N];

IN void build(int k,int l,int r){

    tr[k].l=l;tr[k].r=r;

    if(l==r){

        tr[k].w=e[l];

        return;

    }int mid=(l+r)/;

    build(k*,l,mid);build(k*+,mid+,r);

    tr[k].w=tr[k*].w+tr[k*+].w;

}

IN void down(int k){

    tr[k].f^=;

    tr[k*].w=(tr[k*].r-tr[k*].l+)-tr[k*].w;

    tr[k*+].w=(tr[k*+].r-tr[k*+].l+)-tr[k*+].w;

    tr[k*].f^=;

    tr[k*+].f^=;

}

IN void ask_interval(int k,int l,int r){

    int ll=tr[k].l,rr=tr[k].r,mid=(ll+rr)/;

    if(ll>=l&&rr<=r){

        ans+=tr[k].w;

        return;

    }if(tr[k].f) down(k);

    if(l<=mid) ask_interval(k*,l,r);

    if(r>mid) ask_interval(k*+,l,r);

    tr[k].w=tr[k*].w+tr[k*+].w;

}

IN void change_interval(int k,int l,int r){

    int ll=tr[k].l,rr=tr[k].r,mid=(ll+rr)/;

    if(ll>=l&&rr<=r){

        tr[k].w=(rr-ll+)-tr[k].w;

        tr[k].f^=;

        return;

    }if(tr[k].f) down(k);

    if(l<=mid) change_interval(k*,l,r);

    if(r>mid) change_interval(k*+,l,r);

    tr[k].w=tr[k*].w+tr[k*+].w;

}

int main()

{

    in(n);in(m);

    for(int i=;i<=n;i++)

        scanf("%1d",&e[i]);

    build(,,n);

    while(m--){

        int p,l,r;

        in(p);in(l);in(r);

        if(p==){

            change_interval(,l,r);

        }else {

            ans=,ask_interval(,l,r);

            printf("%d\n",ans);

        }

    }return ;

}