Splay

本文主要是介绍Splay，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 板子题：P3369 【模板】普通平衡树

题目链接：https://www.luogu.com.cn/problem/P3369

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=5e5+11,inf=1<<29;
  4 int n,T,root,tot;
  5 
  6 inline int re_ad() {
  7     char ch=getchar(); int x=0,f=1;
  8     while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
  9     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
 10     return x*f;
 11 }
 12 
 13 struct SplayTree {
 14     struct Node {
 15         int fa,val,siz,cnt,ch[2];
 16     };
 17     Node t[N];
 18     inline void Pushup(int d) {
 19         t[d].siz=t[t[d].ch[0]].siz+t[t[d].ch[1]].siz+t[d].cnt;
 20     }
 21     inline void Rotate(int x) {
 22         int y=t[x].fa,z=t[y].fa;
 23         int k1=(t[z].ch[1]==y),k2=(t[y].ch[1]==x);
 24         t[t[x].ch[k2^1]].fa=y;
 25         t[y].ch[k2]=t[x].ch[k2^1];
 26         t[y].fa=x;
 27         t[x].ch[k2^1]=y;
 28         t[x].fa=z;
 29         t[z].ch[k1]=x;
 30         Pushup(y),Pushup(x);
 31     }
 32     inline void Splay(int x,int goal) {
 33         while(t[x].fa!=goal) {
 34             int y=t[x].fa,z=t[y].fa;
 35             if(z!=goal) (t[y].ch[0]==x)^(t[z].ch[0]==y) ? Rotate(x) : Rotate(y);
 36             Rotate(x);
 37         }
 38         if(!goal) root=x;
 39     }
 40     inline void Insert(int x) {
 41         int u=root,f=0;
 42         while(u && t[u].val!=x) f=u,u=t[u].ch[x>t[u].val];
 43         if(u) ++t[u].cnt;
 44         else {
 45             u=++tot;
 46             if(f) t[f].ch[x>t[f].val]=u;
 47             t[u].fa=f,t[u].val=x;
 48             t[u].cnt=t[u].siz=1;
 49             t[u].ch[0]=t[u].ch[1]=0;
 50         }
 51         Splay(u,0);
 52     }
 53     inline void Find(int x) {
 54         int u=root;
 55         if(!u) return ;
 56         while(t[u].ch[x>t[u].val] && x!=t[u].val) u=t[u].ch[x>t[u].val];
 57         Splay(u,0);
 58     }
 59     inline void Query(int x) {
 60         int lson=t[root].ch[0];
 61         printf("%d\n",t[lson].siz);
 62     }
 63     inline int Next(int d,int flag) {
 64         Find(d);
 65         int u=root;
 66         if(d<t[u].val && flag) return u;
 67         if(d>t[u].val && !flag) return u;
 68         u=t[u].ch[flag];
 69         while(t[u].ch[flag^1]) u=t[u].ch[flag^1];
 70         return u;
 71     }
 72     inline int Get_Pre(int d) {
 73         return t[Next(d,0)].val;
 74     }
 75     inline int Get_Suf(int d) {
 76         return t[Next(d,1)].val;
 77     }
 78     inline void Delete(int d) {
 79         int lst=Next(d,0),nxt=Next(d,1);
 80         Splay(lst,0),Splay(nxt,lst);
 81         int del=t[nxt].ch[0];
 82         if(t[del].cnt>1) --t[del].cnt,Splay(del,0);
 83         else t[nxt].ch[0]=0;
 84     }
 85     inline int Kth(int x) {
 86         int u=root;
 87         if(t[u].siz<x) return 0;
 88         while(1) {
 89             int y=t[u].ch[0];
 90             if(x>t[y].siz+t[u].cnt) x-=t[y].siz+t[u].cnt,u=t[u].ch[1];
 91             else if(t[y].siz>=x) u=y;
 92             else return t[u].val;
 93         }
 94     }
 95 }st;
 96 
 97 int main()
 98 {
 99     int op,x;
100     T=re_ad();
101     st.Insert(inf),st.Insert(-inf);
102     while(T--)
103     {
104         op=re_ad();
105         if(op==1) x=re_ad(),st.Insert(x);
106         else if(op==2) x=re_ad(),st.Delete(x);
107         else if(op==3) x=re_ad(),st.Find(x),st.Query(x);
108         else if(op==4) x=re_ad(),printf("%d\n",st.Kth(x+1));
109         else if(op==5) x=re_ad(),printf("%d\n",st.Get_Pre(x));
110         else if(op==6) x=re_ad(),printf("%d\n",st.Get_Suf(x));
111     }
112     return 0;
113 }

这篇关于Splay的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！