LOJ517「LibreOJ β Round #2」计算几何瞎暴力
要求维护一个全局异或，动态在末尾加元素，询问区间和，全局排序的数据结构。
首先因为是全局异或，这个可以想到直接打标记，然后在末尾加元素可以用一个缓存数组，重点在于全局排序还要区间询问和该怎么办。
根据排序，可以想到 (Trie) 来做，同时区间和其实就是对应 (Trie) 树上的一段，再加之全局异或标记，其实就是树上 0/1 路径的交换。
所以对于已经排好序的存到 (Trie) 里，剩下的搞一个数组缓存并随时维护前缀和即可。
然后区间和就是相当于在 (Trie) 里询问再加上一段前缀和，可以用类似 (Trie) 树上二分的操作来实现。
代码：
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=1e6+5;
int a[N],pos,n,m;
int pre[N][31],ls[N<<1],rs[N<<1],bit[N<<1][31],siz[N<<1],num[N<<1],cnt=1,x,tmpx,dx;
void ins(int k){
++siz[1];
for(int j=0,p=1;j<=30;j++,p<<=1) bit[1][j]+=((k&p)>0);
for(int i=30,t=1<<30,id=1;i>=0;i--,t>>=1){
if(k&t){
if(!rs[id]) rs[id]=++cnt,num[cnt]=num[id]+t;
id=rs[id];
}
else{
if(!ls[id]) ls[id]=++cnt,num[cnt]=num[id];
id=ls[id];
}
for(int j=0,p=1;j<=30;j++,p<<=1) bit[id][j]+=((k&p)>0);
++siz[id];
}
return ;
}
long long GetNum(int t,int k,int id){
if(!k||!id) return 0;
if(k==siz[id]){
long long res=0;
for(int j=0,p=1;j<=30;j++,p<<=1) res+=1ll*p*((p&x)?(k-bit[id][j]):bit[id][j]);
return res;
}
if(t==0){return 1ll*k*(num[id]^x);}
if(dx&t)if(k<=siz[rs[id]]) return GetNum(t>>1,k,rs[id]); else return GetNum(t>>1,siz[rs[id]],rs[id])+GetNum(t>>1,k-siz[rs[id]],ls[id]);
else if(k<=siz[ls[id]]) return GetNum(t>>1,k,ls[id]); else return GetNum(t>>1,siz[ls[id]],ls[id])+GetNum(t>>1,k-siz[ls[id]],rs[id]);
}
signed main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
for(int j=0,p=1;j<=30;j++,p<<=1) pre[i][j]=pre[i-1][j]+((a[i]&p)>0);
}
read(m);int op,k;
while(m--){
read(op);
if(op==1){
read(k);
a[++n]=k^x;
for(int j=0,p=1;j<=30;j++,p<<=1) pre[n][j]=pre[n-1][j]+((a[n]&p)>0);
}
else if(op==3){
int g;read(g);
x^=g,tmpx^=g;
}
else if(op==4){
while(pos<n) ins(a[++pos]);
dx^=tmpx,tmpx=0;
}
else{
int l,r;read(l),read(r);
long long res;
if(r<=pos){
res=GetNum(1<<30,r,1)-GetNum(1<<30,l-1,1);
write(res),putchar('
');
}
else if(l>pos){
res=0;
for(int j=0,p=1;j<=30;j++,p<<=1) res+=1ll*p*((p&x)?(r-l+1-pre[r][j]+pre[l-1][j]):(pre[r][j]-pre[l-1][j]));
write(res),putchar('
');
}
else{
res=GetNum(1<<30,pos,1)-GetNum(1<<30,l-1,1);
for(int j=0,p=1;j<=30;j++,p<<=1) res+=1ll*p*((p&x)?(r-pos-pre[r][j]+pre[pos][j]):(pre[r][j]-pre[pos][j]));
write(res),putchar('
');
}
}
}
return 0;
}