Submission #43144537

---

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3r0SfjC ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using vi=vector<int>;
using pii=pair<int,int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

vi tree[5000000];

struct seg_rangecover{
	int n;
	seg_rangecover(int _n){
		init(_n);
	}
	void init(int _n){
		n=_n;
	}
	void add(int node,int l,int r,int _l,int _r,int u){
		if(l>=_r or r<=_l){
			return;
		}
		if(l>=_l and r<=_r){
			tree[node].emplace_back(u);
			return;
		}
		int m=(l+r)/2;
		add(node*2+1,l,m,_l,_r,u);
		add(node*2+2,m,r,_l,_r,u);
	}
	void add(int l,int r,int u){
		add(0,0,n,l,r,u);
	}
};

struct N{
	int nxt[2]={-1,-1};
	int cnt[2]={0,0};
};

struct Q{
	int typ,x;
};

void slv(){
	int q;
	cin>>q;
	// q=2e5;
	
	vec(Q) qry;
	multiset<int> mst1;
	rep(i,q){
		int typ,x=-1;
		cin>>typ;
		if(typ<3){
			cin>>x;
		}
		// typ=qrand()%3+1;
		// if(typ==1){
		// 	x=qrand()%(int)(100);
		// 	mst1.insert(x);
		// }else if(typ==2){
		// 	if(sz(mst1)){
		// 		x=*prev(mst1.end());
		// 		mst1.erase(mst1.find(x));
		// 	}else{
		// 		typ=1;
		// 		x=qrand()%(int)(100);
		// 	}
		// }
		qry.pb(Q{typ,x});
	}

	seg_rangecover seg(q);
	map<int,vi> lst;
	rep(i,q){
		auto [typ,x]=qry[i];
		if(typ==1){
			lst[x].pb(i);
		}else if(typ==2){
			seg.add(lst[x].back(),i,x);
			lst[x].pop_back();
		}
	}
	for(auto&p:lst){
		while(sz(p.se)){
			seg.add(p.se.back(),q,p.fi);
			p.se.pop_back();
		}
	}

	vi pns(q);
	vec(N) trie;
	trie.pb({});
	multiset<int> mst;
	auto rec=[&](auto self,int node,int l,int r)->void{
		int cnt=0;
		vec(pii) delay;
		vi delay2;
		for(auto x:tree[node]){
			// find minimum
			int cur=2e9;
			if(sz(mst)){
				cur=*mst.begin();
			}
			{
				int val=0;
				int rt=0;
				per(j,30){
					int v=(x>>j&1);
					if(trie[rt].cnt[v]>0){
						rt=trie[rt].nxt[v];
					}else{
						val^=(1<<j);
						rt=trie[rt].nxt[v^1];
					}
					if(rt==-1){
						val=-1;
						break;
					}
					if(val>cur){
						break;
					}
				}
				if(val!=-1){
					mst.insert(val);
					delay2.pb(val);
				}
			}
			// insert in
			{
				int rt=0;
				per(j,30){
					int v=(x>>j&1);
					trie[rt].cnt[v]+=1;
					delay.emplace_back(rt,v);
					if(trie[rt].nxt[v]!=-1){
						rt=trie[rt].nxt[v];
					}else{
						trie[rt].nxt[v]=sz(trie);
						rt=sz(trie);
						trie.pb({});
						cnt+=1;
					}
				}
			}
		}
		if(l==r-1){
			if(sz(mst)){
				pns[l]=*mst.begin();
			}
		}else{
			int m=(l+r)/2;
			self(self,node*2+1,l,m);
			self(self,node*2+2,m,r);
		}
		// for(auto [rt,v]:delay1){
		// 	trie[rt].nxt[v]=-1;
		// }
		for(auto [rt,v]:delay){
			trie[rt].cnt[v]-=1;
			if(trie[rt].cnt[v]==0){
				trie[rt].nxt[v]=-1;
			}
		}
		rep(_,cnt){
			trie.pop_back();
		}
		for(auto x:delay2){
			mst.erase(mst.find(x));
		}
	};
	rec(rec,0,0,q);

	rep(i,q){
		if(qry[i].typ==3){
			cout<<pns[i]<<"\n";
		}
	}
}

signed main(){
_3r0SfjC;
	slv();
}

Submission Info

Judge Result