题解 CF242E 【XOR on Segment】

2018-11-07 19:01:14


Description

给定一个长为 $n(n<=10^5)$ 的数组

数组里的数不超过 $10^6$

有两种操作:

1:求 $sum[l,r]$ ;

2:对 $[l,r]$ 中的所有数和 $x$ 异或

Input

第一行一个整数 $n$ ,代表有一个长度为 $n$ 的数组。

第二行 $n$ 个整数,代表 $a_i$

第三行为一个整数 $m$ ,代表有 $m$ 次操作。

接下来 $m$ 行每行描述一个操作。

Output

对于每一个操作 $1$ ,输出一行代表 $sum[l,r]$ .

这题不错,线段树+二进制拆位

由于异或不具有叠加性,所以不能用 $lazy$ 标记直接异或。

我们记录 $tr[o][i]$ 代表当前节点 $o$ ,二进制位 $i$ 上是 $1$ 的数有多少个。

由于,如果某一二进制位上原来为 $1$ ,且当前异或的数 $x$ ,当前二进制位上也有 $1$ ,那么我们的当前 $tr[o][i]=r-l+1-tr[o][i]$ 。

可以理解为 $01$ 交换。

然后由于 $2^{20}$ 比 $10^6$ 要大。

所以只需要拆到 $20$ 即可。

然后直接计算即可。

PS:记得开 $long \ long$ !

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#define int long long 
#define R register

using namespace std;

const int gz=1e5+8;

inline void in(R int &x)
{
    R int f=1;x=0;char s=getchar();
    while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
    while(isdigit(s)){x=x*10+s-'0';s=getchar();}
    x*=f;
}

int n,tr[gz<<2][21],tg[gz<<2],m;

#define ls o<<1
#define rs o<<1|1

inline void up(R int o)
{
    for(R int i=20;~i;i--)
        tr[o][i]=tr[ls][i]+tr[rs][i];
}

void build(R int o,R int l,R int r)
{
    if(l==r)
    {
        R int x;in(x);
        for(R int i=20;~i;i--)
            if((x>>i)&1)tr[o][i]++;
        return;
    }
    R int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    up(o);
}

inline void down(R int o,R int l,R int r)
{
    if(tg[o]==0)return;
    tg[ls]^=tg[o];tg[rs]^=tg[o];
    R int mid=(l+r)>>1;
    for(R int i=20;~i;i--)
    {
        if((tg[o]>>i)&1)
            tr[ls][i]=mid-l+1-tr[ls][i],
            tr[rs][i]=r-mid-tr[rs][i];
    }
    tg[o]=0;
    return;
}

void change(R int o,R int l,R int r,R int x,R int y,R int k)
{
    if(x<=l and y>=r)
    {
        tg[o]^=k;
        for(R int i=20;~i;i--)
            if((k>>i)&1)
                tr[o][i]=r-l+1-tr[o][i];
        return;
    }
    down(o,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)change(ls,l,mid,x,y,k);
    if(y>mid) change(rs,mid+1,r,x,y,k);
    up(o);
}

int query(R int o,R int l,R int r,R int x,R int y)
{
    if(x<=l and y>=r)
    {
        R int res=0;
        for(R int i=20;~i;i--)
            res+=(1<<i)*tr[o][i];
        return res;
    }
    down(o,l,r);
    R int mid=(l+r)>>1,as=0;
    if(x<=mid)as+=query(ls,l,mid,x,y);
    if(y>mid)as+=query(rs,mid+1,r,x,y);
    return as;
}

signed main()
{
    in(n);build(1,1,n);in(m);
    for(R int opt,l,r,x;m;m--)
    {
        in(opt);
        if(opt==1)
        {
            in(l),in(r);
            printf("%lld\n",query(1,1,n,l,r));
        }
        else
        {
            in(l),in(r),in(x);
            change(1,1,n,l,r,x);
        }
    }
}