# 3224: Tyvj 1728 普通平衡树

## 3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 2566  Solved: 1031

[Submit][Status]

## 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

```  1 var
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;
35           begin
37                   begin
39                        exit;
40                   end;
42                   begin
46                   end
47                else
48                    begin
52                    end;
53           end;
55          begin
59          end;
61           var i,j,k,l,f,r:longint;
62           begin
65                   begin
68                        exit;
69                   end;
71                   begin
74                        exit;
75                   end;
77                   begin
81                   end
82                else
83                    begin
87                    end;
88           end;
90           begin
93                   begin
96                        exit;
97                   end;
99                   begin
102                        exit;
103                   end;
105                   begin
108                        exit;
109                   end;
112           end;
114           begin
119           end;
121          var k:longint;
122          begin
125                  begin
127                       if k=-1 then exit(b[lef[head]]+1) else exit(k);
128                  end
129               else
130                   begin
132                           begin
134                           end
135                        else
136                            begin
138                                 if k=-1 then exit(-1) else exit(b[lef[head]]+1+k);
139                            end;
140                   end;
141          end;
143          begin
147          end;
149          begin
152          end;
154          begin
157          end;
158
159 begin
161      randomize;
163      for i:=1 to  n do
164          begin
166               case l of
167                    1:begin
169                           inc(m);
170                           a[m]:=j;
171                           fix[m]:=random(maxlongint);
172                           lef[m]:=0;rig[m]:=0;b[m]:=1;
174                    end;
175                    2:begin
179                           l:=0;
180                    end;
181                    3:BEGIN
184                           writeln(k);
185                    end;
186                    4:begin
189                    end;
190                    5:begin
193                    end;
194                    6:begin
197                    end;
198               end;
199
200               l:=0;
201          end;
203 end.
204             ```

0 条评论

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

实现功能如下——1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x...

• ### 算法模板——splay区间反转 2

实现功能：同splay区间反转 1（基于BZOJ3223 文艺平衡树） 这次改用了一个全新的模板（HansBug：琢磨了我大半天啊有木有），大大简化了程序，同时...

• ### 1112: [POI2008]砖块Klo

1112: [POI2008]砖块Klo Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1245  Solv...

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

实现功能如下——1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x...

• ### 《剑指offer》第22天：链表成环的新解法

思路：通过hash表来检测节点之前是否被访问过，来判断链表是否成环。这是最容易想到的一种题解了。过于简单，直接上代码，go：

• ### Golang Leetcode 203. Remove Linked List Elements.go

版权声明：原创勿转 https://blog.csdn.net/anakinsun/article/details/89012730

• ### 漫谈递归-回文链表

执行用时: 20 ms, 在Palindrome Linked List的C++提交中击败了42.09% 的用户

• ### python算法与数据结构-栈(43)

栈作为一种数据结构，是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹...

• ### 数据结构基础-链表

数组一样能用来存储数据集合，那为什么用多种数据结构来做一样的事情。因为后来发现数组在处理一些情况下的弊端，所以开始分使用情景用不同的工具干同样的事情。 先说说...