题目大意
维护一个序列，支持动态插入，删除，查询最小异或对。
思路分析
看到查询最小异或对首先想到 01Trie，但 01Trie 不支持删除，考虑暴力套一个线段树分治。
需要预处理出每个元素的存活区间，这里使用了 map<int,vector<int>>。注意，有的元素会存活到最后，需要特判。
时间复杂度为 \(O(n\log n\log V)\)，其中 \(V\) 是值域。
这个做法有较强的可扩展性，非常无脑。
代码
代码非常好写，只有 2k。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N=300300,M=10001000;
#define inf 2147483647
int n,op,in1;
int ans[N],type[N];
map<int,vector<int>> mp;//用于预处理元素存活区间
struct Trie{//递归版 Trie
#define c (x>>bit&1)
int a[M][2],num[M];
int tot;
void insert(int p,int bit,int x){
if(!~bit) return ;
if(!a[p][c]) a[p][c]=++tot;
insert(p=a[p][c],bit-1,x);
num[p]++;
}
void del(int p,int bit,int x){
if(!~bit) return ;
del(p=a[p][c],bit-1,x);
num[p]--;
}
int query(int p,int bit,int x){
if(!~bit) return 0;
bool f=!num[a[p][c]];
return query(a[p][c^f],bit-1,x)+f*(1<<bit);
}
}trie;
struct ST{//线段树
#define mid ((l+r)>>1)
vector<int> a[N<<2];
void add(int p,int l,int r,int x,int y,int k){//增加元素
if(x<=l&&r<=y){a[p].push_back(k);return ;}
if(x<=mid) add(p<<1,l,mid,x,y,k);
if(y>mid) add(p<<1|1,mid+1,r,x,y,k);
}
void dfs(int p,int l,int r,int res){//遍历全树
for(auto it:a[p]){
res=min(res,trie.query(0,30,it));
trie.insert(0,30,it);
}
if(l==r) ans[l]=res;
else{
dfs(p<<1,l,mid,res);//答案下传
dfs(p<<1|1,mid+1,r,res);
}
for(auto it:a[p]) trie.del(0,30,it);
}
}tree;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&op);
if(op==1){
scanf("%d",&in1);
mp[in1].push_back(i);
}
if(op==2){
scanf("%d",&in1);
tree.add(1,1,n,mp[in1].back(),i-1,in1);
mp[in1].pop_back();
}
if(op==3) type[i]=1;
}
for(auto it:mp)
for(auto it2:it.second)
tree.add(1,1,n,it2,n,it.first);//特判最后的元素
tree.dfs(1,1,n,inf);
for(int i=1;i<=n;i++)
if(type[i]) cout<<ans[i]<<'\n';
return 0;
}