洛谷 4883 mzf 的考验

看看 1 操作和 3 操作，这不一平衡树？
但是发现 2 操作没法简单地维护。

异或的话，可以维护子树每个数二进制每一位 1 的个数。
那么做一次异或就是把要异或的这个 d 转为二进制，如果哪一位是 1 就把对应的个数反过来（即修改为数的个数减去这个数）。

然后据说 O(n2) 暴力过掉了？于是卡了时限……
被逼吸氧……

代码：

#pragma GCC optimize (2)
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define ls(p) tree[p].lson
#define rs(p) tree[p].rson
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}

const int N = 1e5;
const int LG = 20;
int n,m;
int p;
struct node
{
    int val,rnd,sz;
    int x,rev;
    int cnt[LG + 5];
    long long sum;
    int lson,rson;
} tree[N + 10];
inline void up(int p)
{
    tree[p].sz = tree[ls(p)].sz + 1 + tree[rs(p)].sz;
    tree[p].sum = tree[ls(p)].sum + tree[p].val + tree[rs(p)].sum;
    for(register int i = 1;i <= LG;++i)
        tree[p].cnt[i] = tree[ls(p)].cnt[i] + ((tree[p].val >> i - 1) & 1) + tree[rs(p)].cnt[i];
}
inline void down(int p)
{
    if(tree[p].rev)
    {
        swap(ls(p),rs(p));
        if(ls(p))
            tree[ls(p)].rev ^= 1;
        if(rs(p))
            tree[rs(p)].rev ^= 1;
        tree[p].rev = 0;
    }
    if(tree[p].x)
    {
        int temp[LG + 5];
        for(register int i = 1;i <= LG;++i)
            temp[i] = (tree[p].x >> i - 1) & 1;
        if(ls(p))
        {
            tree[ls(p)].val ^= tree[p].x,tree[ls(p)].x ^= tree[p].x;
            tree[ls(p)].sum = 0;
            for(register int i = 1;i <= LG;++i)
            {
                if(temp[i])
                    tree[ls(p)].cnt[i] = tree[ls(p)].sz - tree[ls(p)].cnt[i];
                tree[ls(p)].sum += (1LL << i - 1) * tree[ls(p)].cnt[i];
            }
        }
        if(rs(p))
        {
            tree[rs(p)].val ^= tree[p].x,tree[rs(p)].x ^= tree[p].x;
            tree[rs(p)].sum = 0;
            for(register int i = 1;i <= LG;++i)
            {
                if(temp[i])
                    tree[rs(p)].cnt[i] = tree[rs(p)].sz - tree[rs(p)].cnt[i];
                tree[rs(p)].sum += (1LL << i - 1) * tree[rs(p)].cnt[i];
            }
        }
        tree[p].x = 0;
    }
}
void split(int p,int k,int &x,int &y)
{
    if(!p)
    {
        x = y = 0;
        return ;
    }
    down(p);
    if(tree[ls(p)].sz < k)
        x = p,split(rs(p),k - tree[ls(p)].sz - 1,rs(p),y);
    else
        y = p,split(ls(p),k,x,ls(p));
    up(p);
}
int merge(int x,int y)
{
    if(!x || !y)
        return x | y;
    down(x),down(y);
    if(tree[x].rnd < tree[y].rnd)
    {
        rs(x) = merge(rs(x),y);
        up(x);
        return x;
    }
    else
    {
        ls(y) = merge(x,ls(y));
        up(y);
        return y;
    }
}
int main()
{
    srand(19260817);
    read(n),read(m);
    for(register int i = 1;i <= n;++i)
    {
        read(tree[i].val);
        tree[i].sz = 1;
        tree[i].rnd = rand();
        tree[i].sum = tree[i].val;
        for(register int j = 1;j <= LG;++j)
            tree[i].cnt[j] = (tree[i].val >> j - 1) & 1;
        p = merge(p,i);
    }
    int op,l,r,d,x,y,z;
    while(m--)
    {
        read(op),read(l),read(r);
        if(op == 1)
        {
            split(p,r,x,z);
            split(x,l - 1,x,y);
            tree[y].rev ^= 1;
            p = merge(merge(x,y),z);
        }
        else if(op == 2)
        {
            read(d);
            split(p,r,x,z);
            split(x,l - 1,x,y);
            tree[y].val ^= d,tree[y].x ^= d;
            int temp[LG + 5];
            for(register int i = 1;i <= LG;++i)
                temp[i] = (d >> i - 1) & 1;
            tree[y].sum = 0;
            for(register int i = 1;i <= LG;++i)
            {
                if(temp[i])
                    tree[y].cnt[i] = tree[y].sz - tree[y].cnt[i];
                tree[y].sum += (1LL << i - 1) * tree[y].cnt[i];
            }
            p = merge(merge(x,y),z);
        }
        else
        {
            split(p,r,x,z);
            split(x,l - 1,x,y);
            printf("%lld\n",tree[y].sum);
            p = merge(merge(x,y),z);
        }
    }
}