算法模板——平衡树Treap

实现功能如下——1. 插入x数 2. 删除x数(若有多个相同的数,因只删除一个) 3. 查询x数的排名(若有多个相同的数,因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x,且最大的数) 6. 求x的后继(后继定义为大于x,且最小的数)

本程序的实现原理为Treap平衡树

详见BZOJ3224

  1 var
  2    i,j,k,l,m,n,head,ts:longint;f1:text;
  3    a,b,fix,lef,rig:array[0..500000] of longint;
  4 procedure lt(var x:longint);inline;
  5           var f,r:longint;
  6           begin
  7                if (x=0) or (rig[x]=0) then exit;
  8                f:=x;r:=rig[x];
  9                b[r]:=b[f];
 10                b[f]:=b[lef[f]]+1+b[LEF[R]];
 11                rig[f]:=lef[r];
 12                lef[r]:=f;
 13                x:=r;
 14           end;
 15 procedure rt(var x:longint);inline;
 16           var f,l:longint;
 17           begin
 18                if (x=0) or (lef[x]=0) then exit;
 19                f:=x;l:=lef[x];
 20                b[l]:=b[f];
 21                b[f]:=b[rig[f]]+1+b[rig[l]];
 22                lef[f]:=rig[l];
 23                rig[l]:=f;
 24                x:=l;
 25           end;
 26 FUNCTION max(x,y:longint):longint;inline;
 27          begin
 28               if x>y then max:=x else max:=y;
 29          end;
 30 function min(x,y:longint):longint;inline;
 31          begin
 32               if x<y then min:=x else min:=y;
 33          end;
 34 procedure ins(var head:longint;x:longint);
 35           begin
 36                if head=0 then
 37                   begin
 38                        head:=x;
 39                        exit;
 40                   end;
 41                if a[x]<a[head] then
 42                   begin
 43                        ins(lef[head],x);
 44                        b[head]:=b[lef[head]]+b[rig[head]]+1;
 45                        if fix[lef[head]]<fix[head] then rt(head);
 46                   end
 47                else
 48                    begin
 49                         ins(rig[head],x);
 50                         b[head]:=b[lef[head]]+b[rig[head]]+1;
 51                         if fix[rig[head]]<fix[head] then lt(head);
 52                    end;
 53           end;
 54 function getp(head,x:longint):longint;
 55          begin
 56               if head=0 then exit(0);
 57               if a[head]=x then exit(head);
 58               if a[head]>x then exit(getp(lef[head],x)) else exit(getp(rig[head],x));
 59          end;
 60 procedure del(var head:longint);
 61           var i,j,k,l,f,r:longint;
 62           begin
 63                if head=0 then exit;
 64                if (lef[head]=0) then
 65                   begin
 66                        b[head]:=b[rig[head]];
 67                        head:=rig[head];
 68                        exit;
 69                   end;
 70                if rig[head]=0 then
 71                   begin
 72                        b[head]:=b[lef[head]];
 73                        head:=lef[head];
 74                        exit;
 75                   end;
 76                if fix[lef[head]]>fix[rig[head]] then
 77                   begin
 78                        lt(head);
 79                        del(lef[head]);
 80                        b[head]:=b[lef[head]]+b[rig[head]]+1;
 81                   end
 82                else
 83                    begin
 84                         rt(head);
 85                         del(rig[head]);
 86                         b[head]:=b[lef[head]]+b[rig[head]]+1;
 87                    end;
 88           end;
 89 procedure det(var head,x:longint);
 90           begin
 91                if head=0 then exit;
 92                if x=head then
 93                   begin
 94                        del(head);
 95                        b[head]:=b[lef[head]]+b[rig[head]]+1;
 96                        exit;
 97                   end;
 98                if lef[head]=x then
 99                   begin
100                        del(lef[head]);
101                        b[head]:=b[lef[head]]+b[rig[head]]+1;
102                        exit;
103                   end;
104                if rig[head]=x then
105                   begin
106                        del(rig[head]);
107                        b[head]:=b[lef[head]]+b[rig[head]]+1;
108                        exit;
109                   end;
110                if a[x]<a[head] then det(lef[head],x) else det(rig[head],x);
111                b[head]:=b[lef[head]]+b[rig[head]]+1;
112           end;
113 procedure showoff(head:longint);
114           begin
115                if head=0 then exit;
116                showoff(lef[head]);
117                write(a[head],' ');
118                showoff(rig[head]);
119           end;
120 function getrank(head,x:longint):longint;
121          var k:longint;
122          begin
123               if head=0 then exit(-1);
124               if x=a[head] then   //亲们注意了,就是这个地方坑了我好久啊啊啊啊啊啊
125                  begin
126                       k:=getrank(lef[head],x);
127                       if k=-1 then exit(b[lef[head]]+1) else exit(k);
128                  end
129               else
130                   begin
131                        if x<a[head] then
132                           begin
133                                exit(getrank(lef[head],x));
134                           end
135                        else
136                            begin
137                                 k:=getrank(rig[head],x);
138                                 if k=-1 then exit(-1) else exit(b[lef[head]]+1+k);
139                            end;
140                   end;
141          end;
142 function rankget(head,x:longint):longint;
143          begin
144               if head=0 then exit(maxlongint);
145               if (b[lef[head]]+1)=x then exit(a[head]);
146               if (b[lef[head]]+1)<x then exit(rankget(rig[head],x-1-b[lef[head]])) else exit(rankget(lef[head],x))
147          end;
148 function getsuc(head,x:longint):longint;
149          begin
150               if (head=0) then exit(+maxlongint);
151               if (a[head]<=x) then exit(getsuc(rig[head],x)) else exit(min(a[head],getsuc(lef[head],x)));
152          end;
153 function getpre(head,x:longint):longint;
154          begin
155               if (head=0) then exit(-maxlongint);
156               if (a[head]>=x) then exit(getpre(lef[head],x)) else exit(max(a[head],getpre(rig[head],x)));
157          end;
158 
159 begin
160      m:=0;head:=0;
161      randomize;
162      readln(n);
163      for i:=1 to  n do
164          begin
165               read(l);
166               case l of
167                    1:begin
168                           readln(j);
169                           inc(m);
170                           a[m]:=j;
171                           fix[m]:=random(maxlongint);
172                           lef[m]:=0;rig[m]:=0;b[m]:=1;
173                           ins(head,m);
174                    end;
175                    2:begin
176                           readln(j);
177                           k:=getp(head,j);
178                           det(head,k);
179                           l:=0;
180                    end;
181                    3:BEGIN
182                           readln(j);
183                           k:=getrank(head,j);
184                           writeln(k);
185                    end;
186                    4:begin
187                           readln(j);
188                           writeln(rankget(head,j));
189                    end;
190                    5:begin
191                           readln(j);
192                           writeln(getpre(head,j));
193                    end;
194                    6:begin
195                           readln(j);
196                           writeln(getsuc(head,j));
197                    end;
198               end;
199 
200               l:=0;
201          end;
202          readln;
203 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java初学

磁盘调度算法寻道问题

42560
来自专栏desperate633

LeetCode 59. Spiral Matrix IIsolution

9120
来自专栏AI2ML人工智能to机器学习

强化学习体验之小游戏 FlappyBird

在安装完TensorFlow之后(详见” Install TensorFlow in Ubuntu 16.04.1 LTS “), 就可以测试各种深度学习的算法...

11710
来自专栏安恒网络空间安全讲武堂

hackme.inndy.tw的19道web题解(下)

目录 写在前面 ...... dafuq-manager 1 dafuq-manager 2. dafuq-manager 3. wordpress 1. w...

1.5K70
来自专栏人工智能LeadAI

Tensorflow on Spark爬坑指南

由于机器学习和深度学习不断被炒热,Tensorflow作为Google家(Jeff Dean大神)推出的开源深度学习框架,也获得了很多关注。Tensorflow...

64190
来自专栏生信技能树

如何选择聚类模块数目

一般来说,类似K-means聚类算法需要我们提取指定聚类得到的cluster数目。 那么问题来了,如何为聚类选择一个适合的cluster数目呢 ? 很遗憾,上面...

1.4K100
来自专栏xingoo, 一个梦想做发明家的程序员

Elasticsearch查询——布尔查询Bool Query

Elasticsearch在2.x版本的时候把filter查询给摘掉了,因此在query dsl里面已经找不到filter query了。其实es并没有完全抛...

24770
来自专栏生信小驿站

R语言之可视化⑩坐标系统目录

ggplot2可以通过coord_flip()切换x和y轴。例如,如果你想要水平箱形图。 这对长标签也很有用:很难让它们在x轴上不重叠的情况下适合。

13430
来自专栏java初学

磁盘调度算法寻道问题

48340
来自专栏哲学驱动设计

090615 T 数据库范式

帮助记忆五级范式:     一级范式:         消除每个表格中重复的组。         为每套相关的数据建立一个独立的表格。         使用一个...

20850

扫码关注云+社区

领取腾讯云代金券