Codeforces 242E. XOR on Segment （线段树+二进制拆位）

ゝ一世哀愁。 2021-12-14 01:53 217阅读 0赞

## 题意：给出一个序列，有两种操作，一种是计算l到r的和，另一种是让l到r的数全部和x做异或运算。   分析：异或是一种位运算，如果x的第j位是1，那么说明l到r的每个数的第j位都要反转，（0^1=1,1^1=0）,如果是0，那么不变。既然是位运算，那么可不可以将每一位作为线段树单独维护呢？好像可以呢！异或操作的话，相当于是一种区间操作，只需要将l到r的某些位进行反转操作不就行了吗？反转操作什么的，打上lazy tag不就OK啦，求和操作也可以计算出l到r的每一位上有多少个1来算出最后的和。好，那么理一下思路，首先确定建立多少个线段树，数的范围是10^6，也就是说，我们最多只需要建立20个线段树即可，再写好线段树的bulid，update，query三个函数。每个节点上需要维护两个值，一个是该区间有多少个1（用于求和），一个是该区间是否反转（lazy tag）。 ##

## 代码： ##

#include<bits/stdc++.h>
    #define ll long long
    #define N 100010
    using namespace std;
    int n,a[N],res,L,R,T,x;
    int f[N<<2][25],tag[N<<2][25];
    ll b[25],ans;//别忘记long long
    int read(){ int s=0;char c=getchar();
        while(!isdigit(c)) c=getchar();
        while(isdigit(c)){s=(s<<1)+(s<<3)+c-'0';c=getchar();}
        return s;
    }
    void built(int k,int l,int r)
    {
        if(l>r) return;
        if(l==r)
        {
            res=a[l];
            for(int i=0;i<21;i++)//拆位
                if((res>>i)&1) f[k][i]=1;
            return;
        }
        int mid=(l+r)>>1,cur=k<<1;
        built(cur,l,mid);
        built(cur|1,mid+1,r);
        for(int i=0;i<21;i++)
            f[k][i]=f[cur][i]+f[cur|1][i];
        return;
    }
    void push(int k,int l,int r,int p)//p表示第几位
    {
        f[k][p]=(r-l+1)-f[k][p];//区间取反
        if(l!=r)
        {
            int cur=k<<1;
            tag[cur][p]^=1;
            tag[cur|1][p]^=1;
        }
        tag[k][p]=0;
    }
    void Modify(int k,int l,int r,int p)//p同上
    {
        if(tag[k][p]) push(k,l,r,p);
        if(r<L||R<l) return;
        if(L<=l&&r<=R)
        {
            push(k,l,r,p);
            return;
        }
        int mid=(l+r)>>1,cur=k<<1;
        Modify(cur,l,mid,p);
        Modify(cur|1,mid+1,r,p);
        f[k][p]=f[cur][p]+f[cur|1][p];
    }
    void Query(int k,int l,int r)//查询，所有位的懒标记都要下放
    {
        for(int i=0;i<21;i++)
            if(tag[k][i]) push(k,l,r,i);
        if(r<L||R<l) return;
        if(L<=l&&r<=R)
        {
            for(int i=0;i<21;i++) ans+=f[k][i]*b[i];
            return;
        }
        int mid=(l+r)>>1,cur=k<<1;
        Query(cur,l,mid);
        Query(cur|1,mid+1,r);
    }
    int main()
    {
        int i,j;b[0]=1;
        for(i=1;i<=21;i++) b[i]=b[i-1]<<1;//初不初始化都可以，就是上面b[i]要变成1<<i
        n=read();
        for(i=1;i<=n;i++) a[i]=read();
        built(1,1,n);
        T=read();
        while(T--)
        {
            if(read()==1)
            {
                L=read();R=read();ans=0;
                Query(1,1,n);
                printf("%lld\n",ans);
            }
            else
            {
                L=read();R=read();x=read();
                for(i=0;i<21;i++)//判断x的第i位是不是1，并进行修改
                    if((x>>i)&1) Modify(1,1,n,i);
            }
        }
        return 0;
    }

# #