Treap

无旋转Treap

有旋转Treap

参考题目

P3369 【模板】普通平衡树

https://www.luogu.com.cn/problem/P3369

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

  1. 插入 xx 数
  2. 删除 xx 数(若有多个相同的数，因只删除一个)
  3. 查询 xx 数的排名(排名定义为比当前数小的数的个数 +1+1 )
  4. 查询排名为 xx 的数
  5. 求 xx 的前驱(前驱定义为小于 xx，且最大的数)
  6. 求 xx 的后继(后继定义为大于 xx，且最小的数)

输入格式

第一行为 nn，表示操作的个数,下面 nn 行每行有两个数 opt\text{opt} 和 xx，opt\text{opt} 表示操作的序号( 1≤opt≤61 \leq \text{opt} \leq 6 )

输出格式

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

样例 #1

样例输入 #1
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
样例输出 #1
106465
84185
492737

提示

【数据范围】
对于 100%100\% 的数据，1≤n≤1051\le n \le 10^5，∣x∣≤107|x| \le 10^7

来源：Tyvj1728 原名：普通平衡树

在此鸣谢

参考代码

题解

P3835 【模板】可持久化平衡树

https://www.luogu.com.cn/problem/P3835

题目背景

本题为题目 普通平衡树 的可持久化加强版。

数据已经经过强化

感谢@Kelin 提供的一组hack数据

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个可重整数集合，其中需要提供以下操作（ 对于各个以往的历史版本 ）：

1、 插入 xx

2、 删除 xx（若有多个相同的数，应只删除一个，如果没有请忽略该操作）

3、 查询 xx 的排名（排名定义为比当前数小的数的个数 +1+1）

4、查询排名为 xx 的数

5、 求 xx 的前驱（前驱定义为小于 xx，且最大的数，如不存在输出 −231+1-2^{31}+1 ）

6、求 xx 的后继（后继定义为大于 xx，且最小的数，如不存在输出 231−12^{31}-1 ）

和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本。（操作3, 4, 5, 6即保持原版本无变化）

每个版本的编号即为操作的序号（版本0即为初始状态，空树）

输入格式

第一行包含一个正整数 nn ，表示操作的总数。

接下来 nn 行，每行包含三个整数，第 ii 行记为 vi,opti,xiv_i, \text{opt}_i, x_i。

viv_i 表示基于的过去版本号，opti\text{opt}_i 表示操作的序号， xix_i 表示参与操作的数值

输出格式

每行包含一个整数，依次为各个 3,4,5,63,4,5,6 操作所对应的答案

样例 #1

样例输入 #1
10
0 1 9
1 1 3
1 1 10
2 4 2
3 3 9
3 1 2
6 4 1
6 2 9
8 6 3
4 5 8
样例输出 #1
9
1
2
10
3

提示

【数据范围】
对于 28%28\% 的数据，1≤n≤101 \leq n \leq 10；
对于 44%44\% 的数据，1≤n≤2×1021 \leq n \leq 2\times {10}^2；
对于 60%60\% 的数据， 1≤n≤3×1031 \leq n \leq 3\times {10}^3；
对于 84%84\% 的数据， 1≤n≤1051 \leq n \leq {10}^5；
对于 92%92\% 的数据， 1≤n≤2×1051 \leq n \leq 2\times {10}^5；
对于 100%100\% 的数据， 1≤n≤5×1051 \leq n \leq 5 \times 10^5 , ∣xi∣≤109|x_i| \leq {10}^9，0≤vi<i0 \le v_i < i，1≤opt≤61\le \text{opt} \le 6。

经实测，正常常数的可持久化平衡树均可通过，请各位放心

样例说明：

共 1010 次操作，1111 个版本，各版本的状况依次是：

  1. [][]

  2. [9][9]

  3. [3,9][3, 9]

  4. [9,10][9, 10]

  5. [3,9][3, 9]

  6. [9,10][9, 10]

  7. [2,9,10][2, 9, 10]

  8. [2,9,10][2, 9, 10]

  9. [2,10][2, 10]

  10. [2,10][2, 10]

  11. [3,9][3, 9]

参考代码

题解

P6136 【模板】普通平衡树（数据加强版）

https://www.luogu.com.cn/problem/P6136

题目背景

本题是 P3369 数据加强版，扩大数据范围并增加了强制在线。

题目的输入、输出和原题略有不同，但需要支持的操作相同。

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些整数，其中需要提供以下操作：

  1. 插入一个整数 xx。
  2. 删除一个整数 xx（若有多个相同的数，只删除一个）。
  3. 查询整数 xx 的排名（排名定义为比当前数小的数的个数 +1+1）。
  4. 查询排名为 xx 的数（如果不存在，则认为是排名小于 xx 的最大数。保证 xx 不会超过当前数据结构中数的总数）。
  5. 求 xx 的前驱（前驱定义为小于 xx，且最大的数）。
  6. 求 xx 的后继（后继定义为大于 xx，且最小的数）。

本题强制在线，保证所有操作合法（操作 22 保证存在至少一个 xx，操作 4,5,64,5,6 保证存在答案）。

输入格式

第一行两个正整数 n,mn,m，表示初始数的个数和操作的个数。

第二行 nn 个整数 a1,a2,a3,…,ana_1,a_2,a_3,\ldots,a_n，表示初始的数。

接下来 mm 行，每行有两个整数 opt\text{opt} 和 x′x'，opt\text{opt} 表示操作的序号（1≤opt≤61 \leq \text{opt} \leq 6），x′x' 表示加密后的操作数。

我们记 last\text{last} 表示上一次 3,4,5,63,4,5,6 操作的答案，则每次操作的 x′x' 都要异或上 last\text{last} 才是真实的 xx。初始 last\text{last} 为 00。

输出格式

输出一行一个整数，表示所有 3,4,5,63,4,5,6 操作的答案的异或和。

样例 #1

样例输入 #1
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4
样例输出 #1
6

提示

样例解释

样例加密前为：

6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 9
3 8
6 1
1 0

限制与约定

对于 100%100\% 的数据，1≤n≤1051\leq n\leq 10^5，1≤m≤1061\leq m\leq 10^6，0≤ai,x<2300\leq a_i,x\lt 2^{30}。

本题输入数据较大，请使用较快的读入方式。

参考代码

题解

  1. Treap
    1. 无旋转Treap
    2. 有旋转Treap
    3. 参考题目
      1. P3369 【模板】普通平衡树
      2. P3835 【模板】可持久化平衡树
      3. P6136 【模板】普通平衡树（数据加强版）
≡