做品牌网站的企业,wordpress怎么添加视频,小视频网站如何建设,wordpress装修题面#xff1a; Description您需要写一种数据结构#xff08;可参考题目标题#xff09;#xff0c;来维护一些数#xff0c;其中需要提供以下操作#xff1a;
1. 插入x数
2. 删除x数(若有多个相同的数#xff0c;因只删除一个)
3. 查询x数的排名(若有多个相同的数 Description您需要写一种数据结构可参考题目标题来维护一些数其中需要提供以下操作
1. 插入x数
2. 删除x数(若有多个相同的数因只删除一个)
3. 查询x数的排名(若有多个相同的数因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x且最大的数)
6. 求x的后继(后继定义为大于x且最小的数)Input第一行为n表示操作的个数,下面n行每行有两个数opt和xopt表示操作的序号(1opt6)Output对于操作3,4,5,6每行输出一个数表示对应答案Sample Input101 1064654 11 3177211 4609291 6449851 841851 898516 819681 4927375 493598Sample Output10646584185492737HINT1.n的数据范围n1000002.每个数的数据范围[-2e9,2e9] View Code 题解 今天第一次接触平衡二叉树的概念做了一道模版题觉得Treap这东西很神奇啊~ 顾名思义Treapheaptree就是把堆和二叉树结合在了一起。 但是为什么不用一般的二叉树呢为了给我们增大代码量不对是因为普通树原来是log(n)级别的但是经过各种insert啊del啊什么的就可能失去“平衡”节点集中在一侧什么的结果成了一条长链这就把log(n)的算法变成O(n)级的线性了。 而现在的Treap就是解决这个问题的方法之一。 Treap中的节点在满足树的性质左儿子都小右儿子都大之类的的同时还对每个节点加入了一个“优先级”并将节点按照堆的性质排序。这里的优先级采用随机生成的方式所以节点的左右分布是随机的以此保证整棵树的相对平衡。 那我们怎么样对这些节点进行堆的排序呢 这就有一个看起来很厉害的操作了--旋转。 旋转分为左旋和右旋。当我们某个节点的左儿子优先度大于本节点就需要进行右旋右儿子大就左旋。 二叉左旋一棵二叉平衡树的子树根是Root左子树是x右子树的根为RootR右子树的两个孩子树分别为RLeftChild和RRightChild。则左旋后该子树的根为RootR右子树为RRightChild左子树的根为RootRoot的两个孩子树分别为x左和RLeftChild右。二叉右旋一棵二叉平衡树的子树根是Root右子树是x左子树的根为RootL左子树的两个孩子树分别为LLeftChild和LRightChild。则右旋后该子树的根为RootL左子树为LLeftChild右子树的根为RootRoot的两个孩子树分别为LRightChild左和x右。 来自百度百科个人觉得挺容易懂的。 那么问题来了为什么你这么一转还能保持树的性质成立呢为什么不会把节点权小的和大的弄返呢不会把树弄乱吗 这就是旋转的真正厉害之处了----可以发现旋转前后该子树的中序遍历是不变的就是说并不会改变数列的大小顺序。我也不是很懂具体是为什么能这样但是确实很厉害。 剩下就没什么了树嘛插入删除的都比较基础。 放代码 1 #includebits/stdc.h2 using namespace std;3 const int maxn100010,inf100000000;4 int cnt,ret,n,t1,t2,root;5 struct treap{6 int lc,rc,key,pri,siz,val;7 /*key是关键字权pri是优先度siz为子树大小val表示key这个数有几个*/8 }a[maxn];9 void pushup(int o){10 a[o].siza[a[o].lc].siza[a[o].rc].siza[o].val;11 return;12 }13 void lturn(int o){14 int ta[o].rc;15 a[o].rca[t].lc;16 a[t].lco;17 a[t].siza[o].siz;18 pushup(o);19 ot;20 return;21 }22 void rturn(int o){23 int ta[o].lc;24 a[o].lca[t].rc;25 a[t].rco;26 a[t].siza[o].siz;27 pushup(o);28 ot;29 return;30 }31 void insert(int o,int t){32 if(!o){33 ocnt;34 a[o](treap){0,0,t,rand(),1,1};//rand()随机一个优先度35 return;36 }37 a[o].siz;38 if(ta[o].key)a[o].val;39 else if(ta[o].key){40 insert(a[o].lc,t);41 if(a[a[o].lc].pria[o].pri)rturn(o);42 }43 else{44 insert(a[o].rc,t);45 if(a[a[o].rc].pria[o].pri)lturn(o);//46 }47 return;48 }49 void del(int o,int k){50 if(!o)return;51 if(ka[o].key){52 if(a[o].val1){53 a[o].val--;54 a[o].siz--;55 }56 else if(!(a[o].lc*a[o].rc)){//如果左右只有一个儿子57 oa[o].lca[o].rc;58 }59 else if(a[a[o].lc].pria[a[o].rc].pri){60 lturn(o);61 del(o,k);62 }63 else{64 rturn(o);65 del(o,k);66 }67 }68 else if(ka[o].key)69 {70 --a[o].siz;71 del(a[o].lc,k);72 }73 else74 {75 --a[o].siz;76 del(a[o].rc,k);77 }78 return;79 }80 int query_rank(int o,int k){81 if(!o)return 0;82 if(ka[o].key)return query_rank(a[o].lc,k);83 if(ka[o].key)return a[a[o].lc].siz1;84 return a[a[o].lc].siza[o].valquery_rank(a[o].rc,k);85 }86 int query_num(int o,int k){87 if(!o)return 0;88 if(ka[a[o].lc].siz)return query_num(a[o].lc,k);89 if(ka[a[o].lc].siza[o].val)return a[o].key;90 return query_num(a[o].rc,k-a[a[o].lc].siz-a[o].val);91 }92 void query_pre(int o,int k){93 if(!o)return;94 if(ka[o].key)query_pre(a[o].lc,k);95 else{96 reta[o].key;97 query_pre(a[o].rc,k);98 }99 return;
100 }
101 void query_pos(int o,int k){
102 if(!o)return;
103 if(ka[o].key)query_pos(a[o].rc,k);
104 else{
105 reta[o].key;
106 query_pos(a[o].lc,k);
107 }
108 return;
109 }
110 int main(){
111 scanf(%d,n);
112 srand(n);
113 for(int i1;in;i){
114 scanf(%d%d,t1,t2);
115 if(t11)insert(root,t2);
116 else if(t12)del(root,t2);
117 else if(t13)printf(%d\n,query_rank(root,t2));
118 else if(t14)printf(%d\n,query_num(root,t2));
119 else if(t15){
120 ret-inf;
121 query_pre(root,t2);
122 printf(%d\n,ret);
123 }
124 else if(t16){
125 retinf;
126 query_pos(root,t2);
127 printf(%d\n,ret);
128 }
129 }
130 return 0;
131 } 转载于:https://www.cnblogs.com/Requiescat/p/7545898.html
