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

本文主要是介绍「LibreOJ β Round #2」计算几何瞎暴力（0/1 trie），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

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

写到一半发现出问题了

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

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

#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;
}