【模板】普通平衡树 洛谷P3369 splay

正文

这题比较裸，直接套伸展树模板。具体可以到这里学一学

#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>using namespace std;int n;struct tree{int same,c,son[2],f,v;}s[110010];int root=0;int tot=0;void update(int x){s[x].c=s[s[x].son[0]].c+s[s[x].son[1]].c+s[x].same;return ;}int findip(int x){int now=root;while(x!=s[now].v){if(x<s[now].v){if(s[now].son[0]==0) break;now=s[now].son[0];}else{if(s[now].son[1]==0) break;now=s[now].son[1];}}return now;}void add(int v,int x){tot++;s[tot].v=v;s[tot].f=x;s[tot].c=s[tot].same=1;s[tot].son[0]=s[tot].son[1]=0;if(v<s[x].v) s[x].son[0]=tot;else s[x].son[1]=tot;return ;}void rotate(int x,int w){int f=s[x].f,ff=s[f].f;s[f].son[1-w]=s[x].son[w];if(s[x].son[w]!=0) s[s[x].son[w]].f=f;if(s[ff].son[0]==f) s[ff].son[0]=x;else s[ff].son[1]=x;s[x].f=ff;s[f].f=x;s[x].son[w]=f;update(f);update(x);}void splay(int x,int tar){while(s[x].f!=tar){int f=s[x].f,ff=s[f].f;if(ff==tar){if(s[f].son[0]==x) rotate(x,1);else rotate(x,0);}else{if(s[ff].son[0]==f){if(s[f].son[0]==x) {rotate(f,1);rotate(x,1);}else {rotate(x,0);rotate(x,1);}}else{if(s[f].son[0]==x) {rotate(x,1);rotate(x,0);}else {rotate(f,0);rotate(x,0);}}}}if(tar==0) root=x;}void insert(int x){if(root==0){add(x,0);root=tot;return ;}int ip=findip(x);if(s[ip].v==x){s[ip].same++;update(ip);splay(ip,0);}else{add(x,ip);update(ip);splay(tot,0);}}void del(int x){int ip=findip(x);splay(ip,0);if(s[ip].v!=x) return ; if(s[ip].same>1) s[ip].same--,update(ip);else if(s[ip].son[0]==0 && s[ip].son[1]==0) root=0,tot=0;else if(s[ip].son[0]!=0 && s[ip].son[1]==0) {root=s[ip].son[0];s[s[ip].son[0]].f=0;}else if(s[ip].son[0]==0 && s[ip].son[1]!=0) {root=s[ip].son[1];s[s[ip].son[1]].f=0;}else{int p=s[ip].son[0];while(s[p].son[1]!=0) p=s[p].son[1];splay(p,ip);root=p;s[p].f=0;s[s[ip].son[1]].f=p;s[p].son[1]=s[ip].son[1];update(p);}}int find_rank(int x){int ip=findip(x);splay(ip,0);return s[s[ip].son[0]].c+1;}int find_num(int x){int now=root;while(1){if(x<=s[s[now].son[0]].c) now=s[now].son[0];else if(x>s[now].same+s[s[now].son[0]].c){x-=s[now].same+s[s[now].son[0]].c;now=s[now].son[1];}else break;}return s[now].v;}int find_last(int x){int ip=findip(x);splay(ip,0);if(x<=s[ip].v && s[ip].son[0]!=0){ip=s[ip].son[0];while(s[ip].son[1]!=0) ip=s[ip].son[1]; }if(x<=s[ip].v) return 0;return s[ip].v;}int find_next(int x){int ip=findip(x);splay(ip,0);if(s[ip].v<=x && s[ip].son[1]!=0){ip=s[ip].son[1];while(s[ip].son[0]!=0) ip=s[ip].son[0];}if(s[ip].v<=x) return 0;return s[ip].v;}int main(){scanf("%d",&n);for(int i=1;i<=n;i++){int t,x;scanf("%d %d",&t,&x);if(t==1) insert(x);else if(t==2) del(x);else if(t==3) printf("%d\n",find_rank(x));else if(t==4) printf("%d\n",find_num(x));else if(t==5) printf("%d\n",find_last(x));else if(t==6) printf("%d\n",find_next(x));}}