loj517 计算几何瞎暴力

在序列上维护4个操作

1.在序列的尾端添加x

2.输出Al~Ar的和

3.将所有数异或x

4.将序列从小到大排序

第一眼看上去是Splay于是头铁硬刚了一发

后来发现splay没法异或

去百度“维护异或  数据结构”

然后看到了Trie树  学习了一个

1.直接插到序列里

2.考虑前缀和  因为Trie树所管辖的下标区间是有序的，所以这里相当于求Trie树中最小的x个数的，记一下每个点下面数字个数（sz）就可以了

3.考虑整体打一个xortag 对于当前存在的xortag 我们将它的每一位分解到Trie树上跑，如果xortag某一位为1，那么其实相当于该位置的左儿子比右儿子大 处理一下即可

4.把序列插到Trie树里

然后瞎暴力/滑稽

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

#include<set>

#include<map>

#include<stack>

#define ll long long

#define pi 3.14

#define eps 1e-9

#define INF 2147483233

#define m(a) memset(a,0,sizeof(a))

#define M(a) memset(a,127,sizeof(a))

#define REP(i,m,n) for(int i=1;i<=n;i++)

#define DWN(i,n,m) for(int i=n;i>=1;i++)

#define lowbit(x) x&(-x)

#define POJ(n) while(~scanf("%d",&n) && n)

using namespace std;

const int maxn=1e5,maxh=;

int xortag,n,m;

struct trie

{

    int ch[maxn*maxh][];

    int sz[maxn*maxh];

    int sum[maxn*maxh][maxh];

    int root=;

    int len=;

    int tag=;

    void insert(int x)

    {

        int u=root;

        for(int i=maxh-;i>=;--i)

        {

            int id=((x&(<<i))>);

            if(!ch[u][id]) ch[u][id]=++len;

            u=ch[u][id];

            ++sz[u];

            for(int j=;j<maxh;++j)

                if(x&(<<j)) sum[u][j]++;

        }

    }

    long long getsum(int x)

    {

        long long ans=;

        for(int i=;i<maxh;++i)

            if(xortag&(<<i)) ans+=(sz[x]-sum[x][i])*(1LL<<i);else ans+=sum[x][i]*(1LL<<i);

        return ans;

    }

    long long query(int x)

    {

        if(x==) return ;

        int u=root;

        long long ans=;

        for(int i=maxh-;i>=;--i)

        {

            int l=,r=;

            if(tag&(<<i)) swap(l,r);

            if(x<=sz[ch[u][l]]) u=ch[u][l];

            else

            {

                ans+=getsum(ch[u][l]);

                x-=sz[ch[u][l]];

                u=ch[u][r];

            }

        }

        ans+=getsum(u)/sz[u]*x;

        return ans;

    }

    int getsize()

    {

        return sz[ch[root][]]+sz[ch[root][]];

    }

}Trie;

struct array

{

    int a[maxn+];

    int sum[maxn+][maxh];

    int len=;

    void insert(int x)

    {

        x^=xortag;

        a[++len]=x;

        for(int i=;i<maxh;++i)

            sum[len][i]=sum[len-][i]+((x&(<<i))>);

    }

    long long query(int x)

    {

        long long ans=;

        for(int i=;i<maxh;++i)

            if(xortag&(<<i)) ans+=(x-sum[x][i])*(1LL<<i);else ans+=sum[x][i]*(1LL<<i);

        return ans;

    }

    void transfer()

    {

        Trie.tag=xortag;

        for(int i=;i<=len;++i)

            Trie.insert(a[i]);

        len=;

    }

}Array;

long long query(int x)

{

    if(x<=Trie.getsize()) return Trie.query(x);

    else return Trie.query(Trie.getsize())+

        Array.query(x-Trie.getsize());

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;++i)

    {

        int x;

        scanf("%d",&x);

        Array.insert(x);

    }

    scanf("%d",&m);

    for(int i=;i<=m;++i)

    {

        int op,x,y;

        scanf("%d",&op);

        if(op==)

        {

            scanf("%d",&x);

            Array.insert(x);

        }

        if(op==)

        {

            scanf("%d%d",&x,&y);

            printf("%lld\n",query(y)-query(x-));

        }

        if(op==)

        {

            scanf("%d",&x);

            xortag^=x;

        }

        if(op==) Array.transfer();

    }

    return ;

}