青阳buleeyes @ 2023-03-13 15:21:12
#include<bits/stdc++.h>
const int INF=0x7fffffff;
using namespace std;
const int N=1e6+10;
int root,tot,n,q;
struct splay_tree{
int ff,cnt,ch[2],val,size;
}t[N];
int get(int x){
int y=t[x].ff;
return t[y].ch[0]==x?1:0;
}
void update(int x){
t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;
}
inline void rotate(int x){
int y=t[x].ff,z=t[y].ff,k=t[y].ch[1]==x;
t[z].ch[t[z].ch[1]==y]=x;
t[x].ff=z;
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].ff=y;
t[x].ch[k^1]=y;
t[y].ff=x;
update(y);
}
void splay(int x,int goal){
for(int y=t[x].ff;y=t[x].ff,y!=goal;rotate(x)){
if(t[y].ff!=goal) rotate(get(x)==get(y)?y:x);
}
if(goal==0) root=x;
update(x);
}
inline void find(int x){
int u=root;
if(!u) return;
while(t[u].ch[x>t[u].val]&&x!=t[u].val)
u=t[u].ch[x>t[u].val];
splay(u,0);
}
inline void insert(int x){
int u=root,ff=0;
while(u&&t[u].val!=x){
ff=u;u=t[u].ch[x>t[u].val];
}
if(u) t[u].cnt++,t[u].size++;
else{
u=++tot;
if(ff) t[ff].ch[x>t[ff].val]=u;
t[u].ch[0]=t[u].ch[1]=0;
t[tot].ff=ff;t[tot].val=x;
t[tot].cnt=1;t[tot].size=1;
}
splay(u,0);
}
inline int Next(int x,int f){
find(x);
int u=root;
if(t[u].val>x&&f) return u;
if(t[u].val<x&&!f) return u;
u=t[u].ch[f];
while(t[u].ch[f^1]) u=t[u].ch[f^1];
splay(u,0);
return u;
}
inline void Delete(int x){
int last=Next(x,0);
int next=Next(x,1);
splay(last,0);splay(next,last);
int del=t[next].ch[0];
if(t[del].cnt>1)
t[del].cnt--,t[del].size--,splay(del,0);
else t[next].ch[0]=0;
}
inline int kth(int x){
int u=root;
if(t[u].size<x) return 0;
while(1){
int y=t[u].ch[0];
if(x>t[y].size+t[u].cnt){
x-=t[y].size+t[u].cnt;
u=t[u].ch[1];
}
else{
if(t[y].size>=x) u=y;
else{
return splay(u,0),t[u].val;
}
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>q;
insert(INF),insert(-INF);
int now=0,ans=0;
for(int i=1,j;i<=n;++i)
cin>>j,insert(j);
int op,x;
while(q--){
cin>>op>>x;
x^=now;
if(op==1){
insert(x);
}
else if(op==2){
Delete(x);
}
else if(op==3){
find(x);
now=t[t[root].ch[0]].size;
if(t[root].val<x) now+=t[root].cnt;
ans^=now;
}
else if(op==4){
now=kth(x+1);
ans^=now;
}
else if(op==5){
now=t[Next(x,0)].val;
ans^=now;
}
else{
now=t[Next(x,1)].val,ans^=now;
}
}
cout<<ans;
return 0;
}
by 青阳buleeyes @ 2023-03-15 08:28:42
数组开小了