题解
这道题一开始用的是Treap写的,死活调不出来,题解又全是指针的
然后就用splay来写,发现思路自然了许多
引用自FlierKing
平衡树，需支持五个操作：
1. 将某元素置顶：将元素旋到根，然后将左子树合并到该元素的后继
2. 将某元素置底：将元素旋到根，然后将右子树合并到该元素的前驱
3. 将某元素提前/滞后1位：直接与该元素的前驱/后继交换位置及信息
4. 询问指定元素排名：将元素旋到根，输出size-1
5. 询问指定排名元素：在树上find
| 数组名称 | 数组作用 |
|---|---|
| pos | 保存了编号为i的书在splay中的编号 |
| v | 保存了splay编号为i的节点对应的书的编号 |
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
#include<bits/stdc++.h> using namespace std; const int MAXN=80005; int rt,n,m; int ch[MAXN][2],fa[MAXN],pos[MAXN],v[MAXN],tot,size[MAXN]; int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } void pushup(int x){ size[x]=size[ch[x][0]]+size[ch[x][1]]+1; pos[v[ch[x][0]]]=ch[x][0]; pos[v[ch[x][1]]]=ch[x][1]; } void rotate(int x,int &k){ int y=fa[x],z=fa[y],kind; if(ch[y][0]==x)kind=1; else kind=0; if(k==y)k=x; else { if(ch[z][0]==y)ch[z][0]=x; else ch[z][1]=x; } ch[y][kind^1]=ch[x][kind]; fa[ch[y][kind^1]]=y; ch[x][kind]=y; fa[y]=x; fa[x]=z; pushup(x);pushup(y); } void splay(int x,int &k){ while(x!=k){ int y=fa[x],z=fa[y]; if(y!=k){ if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,k); else rotate(y,k); } rotate(x,k); } } int find(int x,int k){ int s=size[ch[x][0]]; if(k==s+1)return x; if(k<=s)return find(ch[x][0],k); else return find(ch[x][1],k-s-1); } void top(int x){//将某元素置顶 x=pos[x]; splay(x,rt);//将元素旋到根 /*将左子树合并到该元素的后继*/ if(!ch[x][0])return; if(!ch[x][1])ch[x][1]=ch[x][0],ch[x][0]=0; else { int y=find(rt,size[ch[x][0]]+2); fa[ch[rt][0]]=y; ch[y][0]=ch[rt][0]; ch[rt][0]=0; splay(y,rt); } } void bottom(int x){//将某元素置底 x=pos[x]; splay(x,rt);//将元素旋到根 /*将右子树合并到该元素的前驱*/ if(!ch[x][1])return; if(!ch[x][0])ch[x][0]=ch[x][1],ch[x][1]=0; else { int y=find(rt,size[ch[x][0]]); fa[ch[rt][1]]=y; ch[y][1]=ch[rt][1]; ch[rt][1]=0; splay(y,rt); } } void ins(int f,int x){//将某元素提前/滞后1位 if(!f)return; /*与该元素的前驱/后继交换位置及信息*/ splay(pos[x],rt); int y=find(rt,f==1?size[ch[pos[x]][0]]+2:size[ch[pos[x]][0]]); int x1=v[y],x2=pos[x]; swap(pos[x],pos[x1]); swap(v[x2],v[y]); } void geta(int x){//询问指定元素排名 splay(x,rt);//将元素旋到根，输出size-1 printf("%d\n",size[ch[x][0]]); } void insert(int x){ v[++tot]=x;size[tot]=1;pos[x]=tot; ch[tot][0]=ch[tot][1]=0; if(tot>1){ ch[tot-1][1]=tot;fa[tot]=tot-1; splay(tot,rt); } } int main(){ n=read();m=read(); rt=1; for(int i=1;i<=n;i++){ insert(read()); } char s[20]; while(m--){ scanf("%s",s); switch(s[0]){ case 'T': top(read()); break; case 'B': bottom(read()); break; case 'I': ins(read(),read()); break; case 'A': geta(pos[read()]); break; case 'Q'://询问指定排名元素 printf("%d\n",v[find(rt,read())]);//find break; } } return 0; } |