题解 P4883 【mzf的考验】

· · 题解

平衡树。

非常裸的平衡树，带翻转似乎只有平衡树能做了吧（

反正 \texttt{fhq} 天下第一就是了【暴论】

依然是区间翻转打标记，区间查询就维护一个 \texttt{sum} 数组，比较难搞的是这个区间异或，注意到题目中有写：\texttt{d}\in[0,2^{20})，考虑使用常用的套路，即将它拆成一位一位的分别维护，由于只有 20 位，所以可以很轻松地存下来。

（尝试了一下新的毒瘤码风，各位感性理解一下吧qaq）

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define MAXN 100005
#define K 20
#define reg register
#define inl inline
#define int long long
using namespace std;
int n,m,a[MAXN];
struct FHQTreap
{
    int ch[MAXN][2],siz[MAXN],val[MAXN],key[MAXN],tag[MAXN],root,sze,num[MAXN][K+5],fg[MAXN],stk[MAXN],top;
    int sum[MAXN];
    bool rev[MAXN];
    inl void Mxr(reg int rt,reg int v)
    {
        tag[rt]^=v;
        val[rt]^=v;
        sum[rt]=0;
        for(reg int i=0;i<=K;i++) fg[i]=(v>>i)&1;
        for(reg int i=0;i<=K;i++)
        {
            if(fg[i]) num[rt][i]=siz[rt]-num[rt][i];
            sum[rt]+=(1<<i)*num[rt][i];
        }
    }
    inl void Psu(reg int rt)
    {
        siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+1;
        sum[rt]=sum[ch[rt][0]]+sum[ch[rt][1]]+val[rt];
        for(reg int i=0;i<=K;i++) num[rt][i]=num[ch[rt][0]][i]+num[ch[rt][1]][i]+((val[rt]>>i)&1);
    }
    inl void Psd(reg int rt)
    {
        if(rev[rt])
        {
            swap(ch[rt][0],ch[rt][1]);
            if(ch[rt][0]) rev[ch[rt][0]]^=1;
            if(ch[rt][1]) rev[ch[rt][1]]^=1;
            rev[rt]=0;
        }
        if(tag[rt])
        {
            reg int v=tag[rt];
            tag[rt]=0;
            if(ch[rt][0]) Mxr(ch[rt][0],v);
            if(ch[rt][1]) Mxr(ch[rt][1],v);
        }
    }
    int Mrg(reg int x,reg int y)
    {
        if(!x || !y) return x+y;
        if(key[x]<key[y])
        {
            Psd(x);
            ch[x][1]=Mrg(ch[x][1],y);
            Psu(x);
            return x;
        }
        else
        {
            Psd(y);
            ch[y][0]=Mrg(x,ch[y][0]);
            Psu(y);
            return y;
        }
    }
    void Spt(reg int rt,reg int pos,reg int &x,reg int &y)
    {
        if(!rt) x=y=0;
        else
        {
            Psd(rt);
            if(pos<=siz[ch[rt][0]])
            {
                y=rt;
                Spt(ch[rt][0],pos,x,ch[rt][0]);
            }
            else
            {
                x=rt;
                Spt(ch[rt][1],pos-siz[ch[rt][0]]-1,ch[rt][1],y);
            }
            Psu(rt);
        }
    }
    inl int Nwd(reg int v)
    {
        reg int rt=++sze;
        siz[rt]=1;
        val[rt]=v;
        key[rt]=rand();
        tag[rt]=rev[rt]=0;
        ch[rt][0]=ch[rt][1]=0;
        return rt;
    }
    inl int Bld()
    {
        memset(stk,0,sizeof(stk));
        top=0;
        reg int x,pre;
        for(reg int i=1;i<=n;i++)
        {
            x=Nwd(a[i]);
            pre=0;
            while(top && key[stk[top]]>key[x])
            {
                Psu(stk[top]);
                pre=stk[top];
                stk[top--]=0;
            }
            if(top) ch[stk[top]][1]=x;
            ch[x][0]=pre;
            stk[++top]=x;
        }
        while(top) Psu(stk[top--]);
        return stk[1];
    }
    inl void Mdy(reg int l,reg int r,reg int v)
    {
        reg int x,y,z;
        Spt(root,r,x,z);
        Spt(x,l-1,x,y);
        Mxr(y,v);
        root=Mrg(Mrg(x,y),z);
    }
    inl void Rev(reg int l,reg int r)
    {
        reg int x,y,z;
        Spt(root,r,x,z);
        Spt(x,l-1,x,y);
        rev[y]^=1;
        root=Mrg(Mrg(x,y),z);
    }
    inl int Qry(reg int l,reg int r)
    {
        reg int x,y,z;
        Spt(root,r,x,z);
        Spt(x,l-1,x,y);
        reg int res=sum[y];
        root=Mrg(Mrg(x,y),z);
        return res;
    }
}T;
signed main()
{
    scanf("%lld %lld",&n,&m);
    for(reg int i=1;i<=n;i++) scanf("%lld",&a[i]);
    T.root=T.Bld();
    while(m--)
    {
        reg int opt,x,y,z;
        scanf("%lld %lld %lld",&opt,&x,&y);
        if(opt==1) T.Rev(x,y);
        else if(opt==2)
        {
            scanf("%lld",&z);
            T.Mdy(x,y,z);
        }
        else if(opt==3) printf("%lld\n",T.Qry(x,y));
    }
    return 0;
}