XOR and OR 题解

Gold14526 · 2025-03-27 21:20:01 · 题解

本文章中 \operatorname{and} 表示按位与运算，\operatorname{or} 表示按位或运算，\operatorname{xor} 表示按位异或运算。

Hint1：考虑求出区间所有子区间按位与的异或和然后 O(1) 转换成子区间按位或的异或和。

Hint2：与和异或有分配率，即 a\operatorname{and}(b\operatorname{xor}c)=(a\operatorname{and}b)\operatorname{xor}(a\operatorname{and}c)。

事实上，知道上面这个差不多就做完了。

先不考虑修改。

我们维护线段树，每个节点上维护以下四个信息：

当我们上传信息时，我们设当前节点为 now，左儿子为 ls，右儿子为 rs，由于与和异或有分配率，我们可以这样计算节点 now 的 xsum 信息：

即左右两边的贡献异或上跨过中点的贡献，跨过中点这一部分相当于是，我们把原来的先求出每个跨过中点的子区间与再异或起来，改成先把两边前后缀与异或起来再与。

同理，xl,xr 也可以简单转移：

如果我们要带修的话，我们再维护取反过后的以上四个信息，异或 x 时交换 x 为 1 的位即可，但是发现直接交换是多带个 \log 的，所以我们考虑一下如何 O(1) 交换 a,b 中 x 为 1 的位，发现我们可以这样操作：

• 设 p=a\operatorname{and}x,q=b\operatorname{and}x。
• 将 a,b 都异或上 p\operatorname{xor}q。

最后我们把这个答案转换为子区间按位或的异或和即可，这一步是简单的。

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
#define sh short
#define csh const short
#define ush unsigned short
#define cush const unsigned short
using namespace std;
inline ll read()
{
    ll x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch-'0');
        ch=getchar();
    }
    return x;
}
inline void print(cll x)
{
    if(x<10)
    {
        putchar(x+'0');
        return;
    }
    cll y=x/10;
    print(y);
    putchar(x-y*10+'0');
}
inline void princh(cll x,const char ch)
{
    print(x);
    putchar(ch);
}
cint N=5e5,H=60;
cll inf=(1<<H)-1;
int n,q;
ll a[N+1];
namespace T{
    struct node{
        int l,r;
        ll tag,xl[2],xr[2],xsum[2],asum[2];
    }t[N<<1|1],z;
    inline void operator^=(node &x,cll y)
    {
        ll tmp;
        x.tag^=y;
        tmp=(x.xl[0]&y)^(x.xl[1]&y);
        x.xl[0]^=tmp,x.xl[1]^=tmp;
        tmp=(x.xr[0]&y)^(x.xr[1]&y);
        x.xr[0]^=tmp,x.xr[1]^=tmp;
        tmp=(x.xsum[0]&y)^(x.xsum[1]&y);
        x.xsum[0]^=tmp,x.xsum[1]^=tmp;
        tmp=(x.asum[0]&y)^(x.asum[1]&y);
        x.asum[0]^=tmp,x.asum[1]^=tmp;
    }
    inline node operator&(const node x,const node y)
    {
        z.l=x.l;
        z.r=y.r;
        z.tag=0;
        z.xl[0]=x.xl[0]^(y.xl[0]&x.asum[0]);
        z.xr[0]=y.xr[0]^(x.xr[0]&y.asum[0]);
        z.xsum[0]=x.xsum[0]^y.xsum[0]^(x.xr[0]&y.xl[0]);
        z.asum[0]=x.asum[0]&y.asum[0];
        z.xl[1]=x.xl[1]^(y.xl[1]&x.asum[1]);
        z.xr[1]=y.xr[1]^(x.xr[1]&y.asum[1]);
        z.xsum[1]=x.xsum[1]^y.xsum[1]^(x.xr[1]&y.xl[1]);
        z.asum[1]=x.asum[1]&y.asum[1];
        return z;
    }
    inline void push_down(cint p)
    {
        if(t[p].tag)
        {
            t[p<<1]^=t[p].tag;
            t[p<<1|1]^=t[p].tag;
            t[p].tag=0;
        }
    }
    inline void Build(cint p,cint l,cint r)
    {
        t[p].l=l;
        t[p].r=r;
        if(l==r)
        {
            t[p].xl[0]=t[p].xr[0]=t[p].xsum[0]=t[p].asum[0]=a[l];
            t[p].xl[1]=t[p].xr[1]=t[p].xsum[1]=t[p].asum[1]=a[l]^inf;
            return;
        }
        cint mid=l+r>>1;
        Build(p<<1,l,mid);
        Build(p<<1|1,mid+1,r);
        t[p]=t[p<<1]&t[p<<1|1];
    }
    inline void build()
    {
        Build(1,1,n);
    }
    inline void Update(cint p,cint l,cint r,cll x)
    {
        if(t[p].l>r||t[p].r<l)return;
        if(t[p].l>=l&&t[p].r<=r)
        {
            t[p]^=x;
            return;
        }
        push_down(p);
        Update(p<<1,l,r,x);
        Update(p<<1|1,l,r,x);
        t[p]=t[p<<1]&t[p<<1|1];
    }
    inline void update(cint l,cint r,cll x)
    {
        Update(1,l,r,x);
    }
    inline node Ask(cint p,cint l,cint r)
    {
        if(t[p].l>=l&&t[p].r<=r)return t[p];
        push_down(p);
        if(t[p<<1].r<l)return Ask(p<<1|1,l,r);
        if(t[p<<1|1].l>r)return Ask(p<<1,l,r);
        return Ask(p<<1,l,r)&Ask(p<<1|1,l,r);
    }
    inline ll ask(cint l,cint r)
    {
        const node res=Ask(1,l,r);
        return (res.xsum[1]^((1ll*(r-l+1)*(r-l+2)/2&1)*inf));
    }
}
inline void modify()
{
    cint l=read(),r=read();
    cll x=read();
    T::update(l,r,x);
}
inline void query()
{
    cint l=read(),r=read();
    princh(T::ask(l,r),'\n');
}
int main()
{
    // freopen("xaa.in","r",stdin);
    // freopen("xaa.out","w",stdout);
    n=read();
    q=read();
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
    }
    T::build();
    while(q--)
    {
        if(read()==1)modify();
        else query();
    }
    return 0;
}