Yoimiyamwf @ 2023-11-06 16:39:58
RT，感谢神犇！！！！
#include <bits/stdc++.h>
#define in inline
#define rint register int
#define r(a) compilerror::runtimerror(a)
#define w(a) compilerror::wronganswer(a)
#define wl(a) compilerror::wronganswer(a),compilerror::pc('\n')
#define ws(a) compilerror::wronganswer(a),compilerror::pc(' ')
using namespace std;
typedef long long ll;
namespace compilerror{
const int pp2=(1<<20)-1;int pp1=-1;
char buf_in[1<<20],buf_out[1<<20],*p1=buf_in,*p2=buf_in;
in void flush(){fwrite(buf_out,1,pp1+1,stdout);pp1=-1;}
in void pc(const char ch){if(pp1==pp2)flush();buf_out[++pp1]=ch;}
in char gc(){return p1==p2&&(p2=(p1=buf_in)+fread(buf_in,1,1<<20,stdin),p1==p2)?EOF:*p1++;}
template <typename t> in void runtimerror(t &x){
char ch=gc();bool f=false;x=0;
for(;!isdigit(ch);ch=gc()) if(ch=='-') f=true;
for(;isdigit(ch);ch=gc()) x=(x<<3)+(x<<1)+(ch^48);
if(f) x=~x+1;
}
template <typename t> in void wronganswer(t x){
if(!x) pc('0');
else{
static char stk[20];int top=0;
if(x<0) pc('-'),x=~x+1;
while(x) stk[top++]=x%10,x/=10;
while(top--) pc(stk[top]^48);
}
}
}
unordered_map <int,int> cnt;
int n,m,opt,x,last,ans,sz,a,b[100010];
struct splay_tree{
int root,size;
struct node{
int s[2],val,cnt,size,fa;
in void init(int v,int f,int c=1){
fa=f,val=v,size=cnt=c;
}
}tr[1100010];
#define ls s[0]
#define rs s[1]
#define pushup(id) (tr[id].size=tr[id].cnt+tr[tr[id].ls].size+tr[tr[id].rs].size)
in void rotate(int id){
int fa=tr[id].fa,gr=tr[fa].fa,tos=tr[fa].rs==id;
tr[gr].s[tr[gr].rs==fa]=id,tr[id].fa=gr;
tr[fa].s[tos]=tr[id].s[tos^1],tr[tr[id].s[tos^1]].fa=fa;
tr[id].s[tos^1]=fa,tr[fa].fa=id;
pushup(fa),pushup(id);
}
in void splay(int id,int aim){
while(tr[id].fa!=aim){
int fa=tr[id].fa,gr=tr[fa].fa;
if(gr!=aim){
if((tr[fa].rs==id)^(tr[gr].rs==fa)) rotate(id);
else rotate(fa);
}
rotate(id);
}
if(!aim) root=id;
}
int build(int l,int r,int fa){
int id=++size,mid=l+r>>1;
tr[id].init(b[mid],fa,cnt[b[mid]]);
if(l<mid) tr[id].ls=build(l,mid-1,id);
if(r>mid) tr[id].rs=build(mid+1,r,id);
pushup(id);
return id;
}
in void insert(int val){
int id=root,fa=0;
while(id&&tr[id].val!=val) fa=id,id=tr[id].s[val>tr[id].val];
if(id) tr[id].cnt++;
else{
id=++size;
tr[id].init(val,fa);
if(fa) tr[fa].s[val>tr[fa].val]=id;
}
splay(id,0);
}
in void remove(int val){
int id=root,fa;
while(id&&tr[id].val!=val) fa=id,id=tr[id].s[val>tr[id].val];
tr[id].cnt--;
if(!tr[id].cnt) tr[fa].s[val>tr[fa].val]=0;
splay(fa,0);
}
in int query_rank(int val){
int id=root,ans=0;
while(id){
if(tr[id].val>val) id=tr[id].ls;
else if(tr[id].val<val) ans+=tr[tr[id].ls].size+tr[id].cnt,id=tr[id].rs;
else return splay(id,0),ans+tr[tr[id].ls].size+1;
}
return ans+1;
}
in int query_val(int rank){
int id=root;
while(id){
if(tr[tr[id].ls].size>=rank) id=tr[id].ls;
else if(tr[id].cnt+tr[tr[id].ls].size>=rank) return splay(id,0),tr[id].val;
else rank-=tr[id].cnt+tr[tr[id].ls].size,id=tr[id].rs;
}
return INT_MAX;
}
in int query_prev(int val){
int id=root,ans=-INT_MAX;
while(id){
if(tr[id].val>=val) id=tr[id].ls;
else ans=tr[id].val,id=tr[id].rs;
}
return id?max(ans,tr[id].val):ans;
}
in int query_next(int val){
int id=root,ans=-INT_MAX;
while(id){
if(tr[id].val<=val) id=tr[id].rs;
else ans=tr[id].val,id=tr[id].ls;
}
return id?min(ans,tr[id].val):ans;
}
#undef ls
#undef rs
#undef pushup
}t;
int main(){
#ifndef ONLINE_JUDGE
(void)!freopen("cin.in","r",stdin);
// (void)!freopen("cout.out","w",stdout);
#endif
r(n),r(m);
for(rint i=1;i<=n;i++){
r(a);
if(cnt.find(a)==cnt.end()) b[++sz]=a;
cnt[a]++;
}
sort(b+1,b+sz+1);
b[0]=-INT_MAX,b[sz+1]=INT_MAX;
t.root=t.build(0,sz+1,0);
while(m--){
r(opt),r(x);
x^=last;
cout<<opt<<' '<<x<<endl;
switch(opt){
case 1:
t.insert(x);
break;
case 2:
t.remove(x);
break;
case 3:
last=t.query_rank(x)-1;
ans^=last;
break;
case 4:
last=t.query_val(x+1);
ans^=last;
break;
case 5:
last=t.query_prev(x);
ans^=last;
break;
case 6:
last=t.query_next(x);
ans^=last;
break;
}
}
w(ans);
compilerror::flush();
return 0;
}