「LibreOJ β Round #2」计算几何瞎暴力 （0/1 trie）

​​传送门​​

考虑 本身可以实现排序，用 维护，打异或 ，尾部插入，排序就是把尾巴的插入到 中，区间和可以用 类似第 大的方法查一个前缀和

写到一半发现出问题了

前缀和怎么支持全局异或
其实很简单，按每一位维护，维护某一位 1 的个数就可以解决这个问题
复杂度

有两个细节有点坑，就是到 叶子的时候可以存在多个，还有查第 大的时候用的是最后一次排序的异或 ，因为后面打上的 并不影响顺序

#include<bits/stdc++.h>
#define cs const
using namespace std;
cs int N = 2e5 + 5;
typedef long long ll;
int read(){
int cnt = 0, f = 1; char ch = 0;
while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; }
while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();
return cnt * f;
}
int n, m, rt, Xor, Sor;
int b[N], sm[N][32], sz;
namespace T{
cs int N = ::N*30;
int ch[N][2],sz[N],nd,sm[N][32];
void ins(int &x, int v, int i){
if(!x) x=++nd; ++sz[x];
for(int j=0; j<=30; j++) sm[x][j]+=(v>>j&1);
if(i<0) return;
int c=v>>i&1; ins(ch[x][c],v,i-1);
}
ll ask(int x, int k, int i){
if(!k||!x) return 0;
if(i<0){
ll ans=0;
for(int j=0; j<=30; j++){
if((Xor>>j&1)^(sm[x][j]>0)) ans+=(ll)k<<j;
} return ans;
}
int c=Sor>>i&1, vl=sz[ch[x][c]];
if(k<vl) return ask(ch[x][c],k,i-1);
else{
ll ans=ask(ch[x][c^1],k-vl,i-1);
for(int j=0; j<=30; j++){
if(Xor>>j&1) ans+=(ll)(sz[ch[x][c]]-sm[ch[x][c]][j])<<j;
else ans+=(ll)sm[ch[x][c]][j]<<j;
} return ans;
}
}
}
ll qry(int x){
if(!x) return 0;
if(x<=n) return T::ask(rt,x,30);
ll ans=T::ask(rt,n,30); x-=n;
for(int i=0; i<=30; i++){
if(Xor>>i&1) ans+=(ll)(x-sm[x][i])<<i;
else ans+=(ll)sm[x][i]<<i;
} return ans;
}
void upt(int k){
for(int i=0; i<=30; i++)
sm[k][i]=sm[k-1][i]+(b[k]>>i&1);
}
void Sort(){
for(int i=1; i<=sz; i++) T::ins(rt,b[i],30), ++n;
sz = 0; Sor = Xor;
}
int main(){
sz=read();
for(int i=1; i<=sz; i++)
b[i]=read(),upt(i);
m=read();
while(m--){
int op = read();
if(op==1) b[++sz]=read()^Xor, upt(sz);
if(op==2){
int l=read(), r=read();
cout<<qry(r)-qry(l-1)<<'\n';
}
if(op==3) Xor^=read();
if(op==4) Sort();
} return 0;
}