专栏首页HansBug's Lab算法模板——平衡树Treap 2

算法模板——平衡树Treap 2

实现功能:同平衡树Treap 1(BZOJ3224 / tyvj1728)

这次的模板有了不少的改进,显然更加美观了,几乎每个部分都有了不少简化,尤其是删除部分,这个参照了hzwer神犇的写法,在此鸣谢,然后,贴模板走人

  1 var
  2    i,j,k,l,m,n,head,tot:longint;
  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
106      readln(n);tot:=0;head:=0;
107      for i:=1 to n do
108          begin
109               readln(j,k);
110               case j of
111                    1:ins(head,k);
112                    2:del(head,k);
113                    3:writeln(getrank(head,k)+1);
114                    4:writeln(rankget(head,k));
115                    5:writeln(getpre(head,k));
116                    6:writeln(getsuc(head,k));
117               end;
118          end;
119 end.

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3713: [PA2014]Iloczyn

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

    HansBug
  • 1901: Zju2112 Dynamic Rankings

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

    HansBug
  • 2761: [JLOI2011]不重复数字(平衡树)

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

    HansBug
  • Kong 插件加载机制源码解析(下)

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

    poslua
  • 2761: [JLOI2011]不重复数字(平衡树)

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

    HansBug
  • 1901: Zju2112 Dynamic Rankings

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

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

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

    杨奉武
  • SkyWalking学习笔记(Window环境 本地环境)

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

    心莱科技雪雁
  • 欺诈、骗单、玩消失,如何用大数据解决银行这些痛点?

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

    BestSDK
  • 烧光 1000 万,我得到了哪些教训?

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

    人称T客

扫码关注云+社区

领取腾讯云代金券