洛谷 5312 「Ynoi 2011」竞赛实验班

类似权值线段树分裂合并维护区间排序的套路，可以考虑用某个维护权值的数据结构来维护有序的那一段。
而此题涉及异或，考虑 01 Trie。

如果没有 4 操作，用个什么数据结构维护下每一位上 1 的个数就行了，并整体维护一个异或标记。
如果没有 1 操作，异或可能会影响大小关系，但是考虑到异或某一位相当于在 Trie 上把某一层所有左右儿子交换，于是打个标记即可。

综合起来，就是每次排序时就把上一次排序到这一次排序新加的数插入即可。
（我才不会说一开始我排序的时候没更新每次有序段的边界，插入的时候还没异或呢）

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2e5;
const int LG = 30;
int n,m,ls,a[N + 5],sum[N + 5][LG + 5];
int Xor,Tag;
int ch[(N << 4) + 10][2],sz[(N << 4) + 10],cnt[(N << 4) + 10][LG + 5],rt;
void insert(int x,int &cur)
{
    static int tot = 0;
    int p = cur ? cur : (cur = ++tot);
    ++sz[p];
    for(register int i = 0;i < LG;++i)
        cnt[p][i] += (x >> i) & 1;
    for(register int i = LG - 1;~i;--i)
    {
        !ch[p][(x >> i) & 1] && (ch[p][(x >> i) & 1] = ++tot);
        p = ch[p][(x >> i) & 1],++sz[p];
        for(register int j = 0;j < LG;++j)
            cnt[p][j] += (x >> j) & 1;
    }
}
long long query(int k,int p)
{
    if(!k)
        return 0;
    int v = 0;
    long long ret = 0;
    for(register int i = LG - 1;~i;--i)
        if(k <= sz[ch[p][(Tag >> i) & 1]])
            p = ch[p][(Tag >> i) & 1],v |= Tag & (1 << i);
        else
        {
            k -= sz[ch[p][(Tag >> i) & 1]];
            for(register int j = 0;j < LG;++j)
                ret += (long long)((Xor & (1 << j)) ? (sz[ch[p][(Tag >> i) & 1]] - cnt[ch[p][(Tag >> i) & 1]][j]) : cnt[ch[p][(Tag >> i) & 1]][j]) << j;
            p = ch[p][((Tag >> i) & 1) ^ 1],v |= (Tag & (1 << i)) ^ (1 << i);
        }
    return ret + (long long)(v ^ Xor) * k;
}
long long query1(int l,int r)
{
    return query(r,rt) - query(l - 1,rt);
}
long long query2(int l,int r)
{
    long long ret = 0;
    for(register int i = 0;i < LG;++i)
        ret += (long long)((Xor & (1 << i)) ? (r - l + 1 - sum[r][i] + sum[l - 1][i]) : (sum[r][i] - sum[l - 1][i])) << i;
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
    {
        scanf("%d",a + i);
        for(register int j = 0;j < LG;++j)
            sum[i][j] = sum[i - 1][j] + ((a[i] >> j) & 1);
    }
    scanf("%d",&m);
    for(int op,x,y;m;--m)
    {
        scanf("%d",&op);
        if(op == 1)
        {
            scanf("%d",&x),a[++n] = x ^ Xor;
            for(register int i = 0;i < LG;++i)
                sum[n][i] = sum[n - 1][i] + ((a[n] >> i) & 1);
        }
        else if(op == 2)
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",x > ls ? query2(x,y) : (y <= ls ? query1(x,y) : query1(x,ls) + query2(ls + 1,y)));
        }
        else if(op == 3)
            scanf("%d",&x),Xor ^= x;
        else
        {
            for(register int i = ls + 1;i <= n;++i)
                insert(a[i],rt);
            ls = n,Tag = Xor,memset(sum[n],0,sizeof sum[n]);
        }
    }
}