题目
https://www.luogu.com.cn/problem/P6136
思路
板子题，就贴个代码吧，如果需要讲解splay的话珂以评论。
PS:相同的数可以合并在一个树节点，这样求前驱/后继什么的可以排除相同数的干扰，也许也能节省一点时间。
代码
#include<cstdlib>
#define maxn (int)(1e6+1e5+10)
using namespace std;
struct SplayTree{
struct node{
int lson,rson,father,val,size,num;
} tree[maxn];
int cnt,root;
private:
void update(int x){
tree[x].size=tree[tree[x].lson].size+tree[tree[x].rson].size+tree[x].num;
}
void zig(int x){
int y=tree[x].father;
tree[x].father=tree[y].father;
if(tree[y].father){
if(tree[tree[y].father].lson==y) tree[tree[y].father].lson=x;
else tree[tree[y].father].rson=x;
}
int z=tree[x].rson;
if(z) tree[z].father=y;
tree[y].lson=z;
tree[x].rson=y;
tree[y].father=x;
update(y);update(x);
}
void zag(int x){
int y=tree[x].father;
tree[x].father=tree[y].father;
if(tree[y].father){
if(tree[tree[y].father].lson==y) tree[tree[y].father].lson=x;
else tree[tree[y].father].rson=x;
}
int z=tree[x].lson;
if(z) tree[z].father=y;
tree[y].rson=z;
tree[x].lson=y;
tree[y].father=x;
update(y);update(x);
}
void splay(int x){
while(tree[x].father){
int y=tree[x].father,z=tree[y].father;
if(!z){
if(tree[y].lson==x) zig(x);
else zag(x);
}
else{
if(tree[y].lson==x&&tree[z].lson==y){
zig(y);zig(x);
}
else if(tree[y].rson==x&&tree[z].rson==y){
zag(y);zag(x);
}
else if(tree[y].lson==x&&tree[z].rson==y){
zig(x);zag(x);
}
else{
zag(x);zig(x);
}
}
}
root=x;
}
int find(int x,int key){
if(!x) return 0;
if(tree[x].val==key) return x;
if(tree[x].val<key) return find(tree[x].rson,key);
else return find(tree[x].lson,key);
}
void add(int x,int y){
if(!x){
root=y;
return;
}
if(tree[x].val<tree[y].val){
if(tree[x].rson) add(tree[x].rson,y);
else{
tree[x].rson=y;
tree[y].father=x;
}
}
else{
if(tree[x].lson) add(tree[x].lson,y);
else{
tree[x].lson=y;
tree[y].father=x;
}
}
update(x);
return;
}
int dfs(int x,int k){
int t1=tree[tree[x].lson].size;
int t2=tree[x].num;
if(t1<k&&t1+t2>=k) return x;
if(k>t1+t2) return dfs(tree[x].rson,k-t1-t2);
else return dfs(tree[x].lson,k);
}
int find_pre(int x){
while(tree[x].rson)
x=tree[x].rson;
return x;
}
int find_next(int x){
while(tree[x].lson)
x=tree[x].lson;
return x;
}
public:
void clear(){
cnt=root=0;
tree[0].father=tree[0].lson=tree[0].rson=0;
tree[0].num=tree[0].size=tree[0].val=0;
}
int insert(int x){//插入一个整数 x
int t=find(root,x);
if(t){
splay(t);
tree[t].num++;
tree[t].size++;
return t;
}
else{
tree[++cnt].val=x;
tree[cnt].num=1;
tree[cnt].size=1;
tree[cnt].lson=tree[cnt].rson=0;
add(root,cnt);
splay(cnt);
return cnt;
}
}
void erase(int x){//删除一个整数 x
int t=find(root,x);
splay(t);
if(tree[t].num==1){
int ll=tree[t].lson,rr=tree[t].rson;
tree[ll].father=tree[rr].father=0;
if(ll&&rr){
int t2=find_next(rr);
splay(t2);
tree[t2].lson=ll;
tree[ll].father=t2;
update(t2);
}
else if(ll) root=ll;
else if(rr) root=rr;
else root=0;
}
else{
tree[t].num--;
tree[t].size--;
}
}
int rank(int x){//查询整数 x 的排名
int t,ans;
t=insert(x);
ans=tree[tree[t].lson].size+1;
erase(x);
return ans;
}
int pos(int x){//查询排名为 x 的数
int t=dfs(root,x);
splay(t);
return tree[t].val;
}
int pre(int x){//求 x 的前驱
int t,ans;
t=insert(x);
ans=find_pre(tree[t].lson);
erase(x);
return tree[ans].val;
}
int next(int x){//求 x 的后继
int t,ans;
t=insert(x);
ans=find_next(tree[t].rson);
erase(x);
return tree[ans].val;
}
int tot(){
return root;
}
}T;
int main(){
int n,m,i,x,lastans=0,opt,ans=0;
// freopen("T.in","r",stdin);
// freopen("myans.out","w",stdout);
scanf("%d%d",&n,&m);
T.clear();
for(i=1;i<=n;i++){
scanf("%d",&x);
T.insert(x);
}
for(i=1;i<=m;i++){
scanf("%d%d",&opt,&x);
x^=lastans;
if(opt==1){
T.insert(x);
}
else if(opt==2){
T.erase(x);
}
else if(opt==3){
lastans=T.rank(x);
ans^=lastans;
}
else if(opt==4){
lastans=T.pos(x);
ans^=lastans;
}
else if(opt==5){
lastans=T.pre(x);
ans^=lastans;
}
else{
lastans=T.next(x);
ans^=lastans;
}
}
printf("%d
",ans);
// system("pause");
return 0;
}