# 算法模板——平衡树Treap 2

```  1 var
3    a,b,lef,rig,fix:array[0..100010] of longint;
4 function min(x,y:longint):longint;
5          begin
6               if x<y then min:=x else min:=y;
7          end;
8 function max(x,y:longint):longint;
9          begin
10               if x>y then max:=x else max:=y;
11          end;
12 procedure lt(var x:longint);
13           var f,r:longint;
14           begin
15                if (x=0) or (rig[x]=0) then exit;
16                b[rig[x]]:=b[x];b[x]:=b[lef[x]]+b[lef[rig[x]]]+1;
17                f:=x;r:=rig[x];
18                rig[f]:=lef[r];
19                lef[r]:=f;
20                x:=r;
21           end;
22 procedure rt(var x:longint);
23           var f,l:longint;
24           begin
25                if (x=0) or (lef[x]=0) then exit;
26                b[lef[x]]:=b[x];b[x]:=b[rig[x]]+b[rig[lef[x]]]+1;
27                f:=x;l:=lef[x];
28                lef[f]:=rig[l];
29                rig[l]:=f;
30                x:=l;
31           end;
32 function newp(x:longint):longint;
33          begin
34               inc(tot);newp:=tot;
35               a[tot]:=x;b[tot]:=1;
36               lef[tot]:=0;rig[tot]:=0;
37               fix[tot]:=random(maxlongint);
38          end;
39 procedure ins(var x:longint;y:longint);
40           begin
41                if x=0 then
42                   begin
43                        x:=newp(y);
44                        exit;
45                   end;
46                if y<a[x] then
47                   begin
48                        ins(lef[x],y);b[x]:=b[lef[x]]+b[rig[x]]+1;
49                        if fix[lef[x]]<fix[x] then rt(x);
50                   end
51                else
52                    begin
53                         ins(rig[x],y);b[x]:=b[lef[x]]+b[rig[x]]+1;
54                         if fix[rig[x]]<fix[x] then lt(x);
55                    end;
56           end;
57 procedure del(var x:longint;y:longint);
58           begin
59                if x=0 then exit;
60                if a[x]=y then
61                   begin
62                        if lef[x]=0 then x:=rig[x] else
63                        if rig[x]=0 then x:=lef[x] else
64                        if fix[lef[x]]>fix[rig[x]] then
65                           begin
66                                lt(x);del(lef[x],y);
67                                b[x]:=b[lef[x]]+b[rig[x]]+1;
68                           end
69                        else
70                            begin
71                                 rt(x);del(rig[x],y);
72                                 b[x]:=b[lef[x]]+b[rig[x]]+1;
73                            end;
74                   end
75                else if y<a[x] then
76                     begin
77                          del(lef[x],y);
78                          b[x]:=b[lef[x]]+b[rig[x]]+1;
79                     end
80                else begin
81                          del(rig[x],y);
82                          b[x]:=b[lef[x]]+b[rig[x]]+1;
83                     end;
84           end;
85 function getrank(x,y:longint):longint;
86          begin
87               if x=0 then exit(0);
88               if y>a[x] then exit(b[lef[x]]+1+getrank(rig[x],y)) else exit(getrank(lef[x],y));
89          end;
90 function rankget(x,y:longint):longint;
91          begin
92               if y=(b[lef[x]]+1) then exit(a[x]);
93               if y<(b[lef[x]]+1) then exit(rankget(lef[x],y)) else exit(rankget(rig[x],y-1-b[lef[x]]));
94          end;
95 function getpre(x,y:longint):longint;
96          begin
97               if x=0 then exit(-maxlongint);
98               if a[x]<y then exit(max(a[x],getpre(rig[x],y))) else exit(getpre(lef[x],y));
99          end;
100 function getsuc(x,y:longint):longint;
101          begin
102               if x=0 then exit(maxlongint);
103               if a[x]>y then exit(min(a[x],getsuc(lef[x],y))) else exit(getsuc(rig[x],y));
104          end;
105 begin
107      for i:=1 to n do
108          begin
110               case j of
117               end;
118          end;
119 end.```

0 条评论

• ### 3713: [PA2014]Iloczyn

3713: [PA2014]Iloczyn Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 327  Solve...

• ### 1901: Zju2112 Dynamic Rankings

1901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

• ### 2761: [JLOI2011]不重复数字（平衡树）

2761: [JLOI2011]不重复数字 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2133  So...

• ### Kong 插件加载机制源码解析（下）

这个阶段就比较重要了，首先要执行的就是 core.access.before(ctx) 这个 hook，主要是完成路由的匹配。不过匹配前需要判断当前路由是否是最...

• ### 2761: [JLOI2011]不重复数字（平衡树）

2761: [JLOI2011]不重复数字 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2133  So...

• ### 1901: Zju2112 Dynamic Rankings

1901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

• ### 9-开发板接入小五物联实现远程控制(Wi-Fi模块)

这一节为教程最终版功能演示,现在不必深究,早晚自己全部都会实现的(静静的跟着我学哈)

• ### SkyWalking学习笔记(Window环境 本地环境)

基于 Windows 环境使用 SkyAPM-dotnet 来介绍一下 SkyWalking， SkyAPM-dotnet 是 SkyWalking 的 .NE...

• ### 欺诈、骗单、玩消失，如何用大数据解决银行这些痛点？

银行的问题总是循环往复地出现。打开任何一家新闻网站或者报纸，我们都能看到一篇又一篇关于银行问题的报道。欺诈、英国退欧引发的不良影响、各式各样的金融危机和违规行为...

• ### 烧光 1000 万，我得到了哪些教训？

T客汇官网：tikehui.com 原文作者：Matt Munson 编译：徐婧欣 ? 起步良好的 Twenty20，在短时间内就烧光了 1000 万资金，这家...