3224: Tyvj 1728 普通平衡树

3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 2566  Solved: 1031

[Submit][Status]

Description

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 1. 插入x数 2. 删除x数(若有多个相同的数,因只删除一个) 3. 查询x数的排名(若有多个相同的数,因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x,且最大的数) 6. 求x的后继(后继定义为大于x,且最小的数)

Input

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

Output

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

Sample Input

10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598

Sample Output

106465 84185 492737

HINT

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

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

Source

平衡树

题解:这是一道平衡树裸题,我果断还是用我萌萌哒Treap,可是在大视野上交就在不停的WA。。。然后弄到数据后发现总是3操作(查询x数的排名)求得的值多出那么几名(HansBug:啊啊啊啊啊啊。。。这个问题让我纠结了一晚上且第二天就病倒了有木有TT phile:这种水题我也是醉了)——仔细一想,我原来程序里面3操作(本程序中的getrank操作)忘考虑一种可能了——当当前节点=x时,不见得最佳排名就是当前点的排名(题目中要的是最优排名哦),我最初写的时候虽然也想到了,可是在插入操作时我是规定只有小于当前点的点才能去左边的啊——可是更重要的是,就算你ins严格遵守了这一规则,但是完全有可能在删除操作中被打乱了——也就是说经过了无数次折腾之后的树未必完全符合插入操作时的规则。。。这样子问题就解决了,别的不难写。。。(HansBug:这个问题估计会坑到无数的treap党有木有。。。希望大家引以为戒么么哒,还有代码有点长么么哒)

  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                        if lef[head]=0 then lef[head]:=x else 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                         if rig[head]=0 then rig[head]:=x else 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.
204             

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ3624: [Apio2008]免费道路(最小生成树)

这棵树上有一些0边是必须要选的,我们先把他们找出来,如果数量$\geqslant k$显然无解

10130
来自专栏小樱的经验随笔

BZOJ 1293: [SCOI2009]生日礼物【单调队列】

1293: [SCOI2009]生日礼物 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2534  Solv...

26650
来自专栏数据结构与算法

树上倍增求LCA及例题

先瞎扯几句 树上倍增的经典应用是求两个节点的LCA 当然它的作用不仅限于求LCA,还可以维护节点的很多信息 求LCA的方法除了倍增之外,还有树链剖分、离线tar...

37760
来自专栏龙首琴剑庐

Java基准测试利器OpenJDK-JMH

60790
来自专栏编程

Python基础原理:FP-growth算法的构建

和Apriori算法相比,FP-growth算法只需要对数据库进行两次遍历,从而高效发现频繁项集。对于搜索引擎公司而言,他们需要通过查看互联网上的用词,来找出经...

33300
来自专栏数据结构与算法

Link-Cut-Tree(LCT)详解

LCT是一种解决动态树问题的方法,由tarjan(为什么又是他)在1982年提出,最原始的论文在这里,在论文中,tarjan除了介绍了均摊复杂度为$O(log^...

594130
来自专栏HansBug's Lab

算法模板——二分图匹配

实现功能为二分图匹配 原理:匈牙利算法,核心思想——匹配上了就配,没直接匹配上也要通过前面的腾出位置让这个匹配上(详见:趣写算法系列之——匈牙利算法) 本程序以...

37240
来自专栏聊聊技术

原 2015 Multi-Universi

355120
来自专栏Java技术栈

Spring Boot 配置随机数那些小技巧

org.springframework.boot.context.config.RandomValuePropertySource

13730
来自专栏marsggbo

Udacity并行计算课程笔记-The GPU Hardware and Parallel Communication Patterns

本小节笔记大纲: 1.Communication patterns gather,scatter,stencil,transpose 2.GPU hardwa...

24060

扫码关注云+社区

领取腾讯云代金券