首页 > 代码库 > P3369 【模板】普通平衡树（Treap/SBT）

P3369 【模板】普通平衡树（Treap/SBT）

2024-10-22 15:35:02   211人阅读

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

  1. 插入x数

  2. 删除x数(若有多个相同的数，因只删除一个)

  3. 查询x数的排名(若有多个相同的数，因输出最小的排名)

  4. 查询排名为x的数

  5. 求x的前驱(前驱定义为小于x，且最大的数)

  6. 求x的后继(后继定义为大于x，且最小的数)

输入输出格式

输入格式：

 

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

 

输出格式：

 

对于操作3,4,5,6每行输出一个数，表示对应答案

 

输入输出样例

输入样例#1：
101 1064654 11 3177211 4609291 6449851 841851 898516 819681 4927375 493598
输出样例#1：
10646584185492737

说明

时空限制：1000ms,128M

1.n的数据范围：n<=100000

2.每个数的数据范围：[-1e7,1e7]

来源：Tyvj1728 原名：普通平衡树

在此鸣谢

 

FHQ Treap。。。

这是我迄今为止见过最神奇没有之一的数据结构！。

它可以用简单的两个非旋转操作模拟出BST的所有操作。

unbelievable。

有空要好好写一篇关于这个的博客

 

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<cmath>  5 #include<algorithm>  6 #include<cstdlib>  7 #include<ctime>  8 using namespace std;  9 const int MAXN=100001; 10 static void read(int &n) 11 { 12     char c=‘+‘;int x=0;bool flag=0; 13     while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;} 14     while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+(c-48);c=getchar();} 15     flag==1?n=-x:n=x; 16 } 17 int ch[MAXN][3];// 0左孩子 1右孩子 18 int val[MAXN];// 每一个点的权值 19 int pri[MAXN];// 随机生成的附件权值 20 int siz[MAXN];// 以i为节点的树的节点数量 21 int sz;// 总结点的数量  22 void update(int x) 23 { 24     siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]]; 25 }  26 int new_node(int v) 27 { 28     siz[++sz]=1;// 新开辟一个节点 29     val[sz]=v; 30     pri[sz]=rand();  31     return sz; 32 } 33 int merge(int x,int y)// 合并  34 { 35     if(!x||!y)    return x+y;// x和y中必定有一个是0 36     if(pri[x]<pri[y])// 把x加到左边的树上  37     { 38         ch[x][1]=merge(ch[x][1],y);// 不懂的看GIF图  39         update(x); 40         return x; 41     }  42     else 43     { 44         ch[y][0]=merge(x,ch[y][0]); 45         update(y); 46         return y; 47     } 48 } 49 void split(int now,int k,int &x,int &y) 50 { 51     if(!now) x=y=0;// 到达叶子节点 52     else 53     { 54         if(val[now]<=k)// 分离右子树     55             x=now,split(ch[now][1],k,ch[now][1],y); 56         else  57             y=now,split(ch[now][0],k,x,ch[now][0]); 58         update(now); 59     }  60 } 61 int kth(int now,int k)// 查询排名  62 { 63     while(1) 64     { 65         if(k<=siz[ch[now][0]]) 66             now=ch[now][0];// 在左子树中，且数量小于左子树的大小，迭代寻找 67         else if(k==siz[ch[now][0]]+1) 68             return now;// 找到了 69         else  70             k-=siz[ch[now][0]]+1,now=ch[now][1];// 去右子树找  71     } 72 } 73 int main() 74 { 75     srand((unsigned)time(NULL)); 76     int n; 77     read(n); 78     int root=0,x,y,z; 79     for(int i=1;i<=n;i++) 80     { 81         int how,a; 82         read(how);read(a); 83         if(how==1)// 插入  84         { 85             split(root,a,x,y); 86             root=merge(merge(x,new_node(a)),y); 87         } 88         else if(how==2)//删除x  89         { 90             split(root,a,x,z); 91             split(x,a-1,x,y); 92             y=merge(ch[y][0],ch[y][1]); 93             root=merge(merge(x,y),z); 94         } 95         else if(how==3)//查询x的排名  96         { 97             split(root,a-1,x,y); 98             printf("%d\n",siz[x]+1); 99             root=merge(x,y);100         }101         else if(how==4)// 查询排名为x的数 102         {103             printf("%d\n",val[kth(root,a)]);104         }105         else if(how==5)// 求x的前驱 106         {107             split(root,a-1,x,y);108             printf("%d\n",val[kth(x,siz[x])]);109             root=merge(x,y);110         }111         else if(how==6)// 求x的后继 112         {113             split(root,a,x,y);114             printf("%d\n",val[kth(y,1)]);115             root=merge(x,y);116         }117     }118     return 0;119 }

 

P3369 【模板】普通平衡树（Treap/SBT）


联系
我们