【codeforces 242E】XOR on Segment

【原题题面】传送门

【题面翻译】传送门

【解题思路】

操作涉及到区间求和和区间异或，考虑到异或操作，我们对每个数二进制分解。

把每一位单独提出来做，异或要么取反要么变为不变，对于每一位建一颗线段树，那么原题中的信息维护就相当于：

1.区间取反

2.区间求和

那就打标记传标记好了。。

【code】

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,q,abt,x,y,z;
int a[25][N];
int d[25][N<<2];
long long t[25][N<<2],ans;
inline int read(){
    int x=0,f=1;   char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}
    return x*f;
}
#define ls p<<1
#define rs p<<1|1

inline void B(int l,int r,int p,int k)
{
    if(l==r){t[k][p]=a[k][l];return;}
    int m=l+r>>1;
    B(l,m,ls,k),B(m+1,r,rs,k);
    t[k][p]=t[k][ls]+t[k][rs];
}

inline void U(int l,int r,int p,int k)
{
    if(x<=l&&r<=y){t[k][p]=(r-l+1)-t[k][p],d[k][p]^=1;return;}
    int m=l+r>>1;
    if(d[k][p])
    {
        t[k][ls]=(m-l+1)-t[k][ls],d[k][ls]^=1;
        t[k][rs]=(r-m)-t[k][rs],d[k][rs]^=1;
        d[k][p]=0;
    }
    if(x<=m)U(l,m,ls,k);
    if(y>m)U(m+1,r,rs,k);
    t[k][p]=t[k][ls]+t[k][rs];
}

inline long long A(int l,int r,int p,int k)
{
    if(x<=l&&r<=y)return t[k][p];
    int m=l+r>>1;
    if(d[k][p])
    {
        t[k][ls]=(m-l+1)-t[k][ls],d[k][ls]^=1;
        t[k][rs]=(r-m)-t[k][rs],d[k][rs]^=1;
        d[k][p]=0;
    }
    long long as=0;
    if(x<=m)as+=A(l,m,ls,k);
    if(y>m)as+=A(m+1,r,rs,k);
    return as;
}

int main()
{
    n=read();
    for(int i=1;i<=n;++i)
    {
        z=read();
        for(int j=1;j<=22;++j)
        {
            if(z&1)a[j][i]=1;
            z>>=1;
        }
    }
    for(int i=1;i<=22;++i)B(1,n,1,i);

    q=read();
    for(int i=1;i<=q;++i)
    {
        abt=read(),x=read(),y=read();
        if(abt==1)
        {
            ans=0;
            for(int j=22;j;--j)ans=ans*2+A(1,n,1,j);
            printf("%lld
",ans);
        }
        else
        {
            z=read();
            for(int j=1;j<=22;++j)
            {
                if(z&1)U(1,n,1,j);
                z>>=1;
            }
        }
    }

    return 0;
}