FHQ Treap：用分裂与合并维护有序集合

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

        import random
import sys
from typing import Optional, Tuple, Any

# 建议在包含深层递归的题目中调高递归深度
# sys.setrecursionlimit(200000)


class Node:
    """Treap 节点"""
    __slots__ = ("val", "pri", "size", "l", "r")

    def __init__(self, val: Any, pri: int):
        self.val = val
        self.pri = pri
        self.size = 1
        self.l: Optional["Node"] = None
        self.r: Optional["Node"] = None


class FHQTreap:
    """
    FHQ-Treap（无旋平衡树）
    基于按值分裂 (split) 与合并 (merge) 维护动态有序集合。
    支持：插入、删除单次出现、按值查排名、查第 k 小、查前驱、查后继。
    所有基本操作的期望时间复杂度均为 O(log n)。
    """

    def __init__(self, seed: Optional[int] = 233):
        self.root: Optional[Node] = None
        self.rng = random.Random(seed)

    def _size(self, u: Optional[Node]) -> int:
        return u.size if u is not None else 0

    def _push_up(self, u: Node) -> None:
        """由左右子树大小更新当前节点子树大小"""
        u.size = self._size(u.l) + self._size(u.r) + 1

    def _new_node(self, val: Any) -> Node:
        return Node(val, self.rng.randint(1, 2**31 - 1))

    def split(self, u: Optional[Node], val: Any) -> Tuple[Optional[Node], Optional[Node]]:
        """
        按数值 val 分裂：
        - 左树 x：包含所有节点值 <= val 的节点
        - 右树 y：包含所有节点值 > val 的节点
        """
        if u is None:
            return None, None
        if u.val <= val:
            x, y = self.split(u.r, val)
            u.r = x
            self._push_up(u)
            return u, y
        else:
            x, y = self.split(u.l, val)
            u.l = y
            self._push_up(u)
            return x, u

    def merge(self, x: Optional[Node], y: Optional[Node]) -> Optional[Node]:
        """
        合并两棵树 x 和 y：
        前提：x 中所有节点的值 <= y 中所有节点的值
        依据节点的随机优先级保持大根堆性质
        """
        if x is None or y is None:
            return x if y is None else y
        if x.pri > y.pri:
            x.r = self.merge(x.r, y)
            self._push_up(x)
            return x
        else:
            y.l = self.merge(x, y.l)
            self._push_up(y)
            return y

    def insert(self, val: Any) -> None:
        """插入一个数值 val"""
        x, y = self.split(self.root, val)
        node = self._new_node(val)
        self.root = self.merge(self.merge(x, node), y)

    def delete(self, val: Any) -> None:
        """
        删除一个数值等于 val 的节点（若存在多个同值节点仅删除其中一个）。
        通过将集合切为 (< val)、(== val)、(> val) 三部分，丢弃 (== val) 的一个节点后拼回。
        """
        x, z = self.split(self.root, val)
        x, y = self.split(x, val - 1)
        if y is not None:
            # 丢弃 y 的根节点，将其左右子树合并
            y = self.merge(y.l, y.r)
        self.root = self.merge(self.merge(x, y), z)

    def rank(self, val: Any) -> int:
        """
        查询数值 val 在集合中的排名（小于 val 的元素个数 + 1）。
        采用 BST 遍历，常数小于 split/merge 且无需改变树结构。
        """
        u = self.root
        ans = 0
        while u is not None:
            if u.val < val:
                ans += self._size(u.l) + 1
                u = u.r
            else:
                u = u.l
        return ans + 1

    def kth(self, k: int) -> Any:
        """
        查询集合中第 k 小的元素（1-based）。
        若 k 超出合法范围 [1, size()] 则抛出 IndexError。
        """
        if not (1 <= k <= self.size()):
            raise IndexError(f"kth index {k} out of range (size={self.size()})")
        u = self.root
        while u is not None:
            l_sz = self._size(u.l)
            if k <= l_sz:
                u = u.l
            elif k == l_sz + 1:
                return u.val
            else:
                k -= l_sz + 1
                u = u.r
        raise IndexError("kth not found")

    def pre(self, val: Any) -> Optional[Any]:
        """
        查询 val 的前驱（小于 val 的最大值）。
        若不存在严格小于 val 的值，返回 None。
        """
        u = self.root
        ans = None
        while u is not None:
            if u.val < val:
                ans = u.val
                u = u.r
            else:
                u = u.l
        return ans

    def succ(self, val: Any) -> Optional[Any]:
        """
        查询 val 的后继（大于 val 的最小值）。
        若不存在严格大于 val 的值，返回 None。
        """
        u = self.root
        ans = None
        while u is not None:
            if u.val > val:
                ans = u.val
                u = u.l
            else:
                u = u.r
        return ans

    def size(self) -> int:
        """返回集合中的节点总数"""
        return self._size(self.root)

    def __len__(self) -> int:
        return self.size()

    def empty(self) -> bool:
        """判断集合是否为空"""
        return self.root is None

    def clear(self) -> None:
        """清空平衡树"""
        self.root = None
    

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202

        """纯函数式（persistent / immutable）FHQ-Treap。

函数式要点：
1. 树是**值**，不是对象状态 —— 没有 class 持有 root，全是 free function。
2. split / merge 是纯函数：Tree × Key -> Tree，不修改任何已有节点，
   而是返回**结构共享**的新树。
3. 递归代替循环，match 解构代替属性访问。
4. 副产品：天然获得 persistence —— 每个历史版本都还在，可回溯。

代价：每次操作 O(log n) 个新节点，常数比原地修改大。

键约定：键取整数（Num 的离散子集）。因此 split 只需要一个原语 ——
按 "<= v" 分裂，"< v" 用 v - 1 表达。见 split_lt 的说明。
"""

from __future__ import annotations

import random
from typing import Any, NamedTuple


class Node(NamedTuple):
    """不可变节点。sz 在构造时算好，所以 size 是 O(1)。"""

    v: Any
    p: float
    l: Node | None
    r: Node | None
    sz: int


Tree = Node | None


# ---------- 构造 ----------

def size(t: Tree) -> int:
    return t.sz if t is not None else 0


def node(v: Any, p: float, l: Tree, r: Tree) -> Node:
    return Node(v, p, l, r, 1 + size(l) + size(r))


def leaf(v: Any, p: float | None = None) -> Node:
    return Node(v, random.random() if p is None else p, None, None, 1)


# ---------- 核心：split / merge ----------

def split_le(t: Tree, v: Any) -> tuple[Tree, Tree]:
    """左树所有值 <= v，右树所有值 > v。

    唯一的 split 原语，只依赖键的序关系（<=）。
    """
    match t:
        case None:
            return None, None
        case Node(x, p, l, r, _) if x <= v:
            a, b = split_le(r, v)
            return node(x, p, l, a), b
        case Node(x, p, l, r, _):
            a, b = split_le(l, v)
            return a, node(x, p, b, r)


def split_lt(t: Tree, v: Any) -> tuple[Tree, Tree]:
    """左树所有值 < v，右树所有值 >= v。

    由 split_le 导出，依赖整数键的离散性：
        x < v  <=>  x <= v - 1
    即 v 的前驱恰为 v - 1。

    成立条件（键为整数时全部满足）：
      - 键离散，不存在介于 v-1 与 v 之间的值
      - 键可减，v - 1 有意义
    对 float 键不成立（0.3 的前驱不是 -0.7），对 str / tuple 键不可减。
    """
    return split_le(t, v - 1)


# 参考实现：不经 v - 1 的通用版 split_lt。
# 与上面的 split_le(t, v - 1) 在整数键上结果逐节点相同，
# 但只依赖键的序关系（<），不依赖离散性与减法。
# 需要支持 float / str / tuple 等一般全序键时，换用这个版本即可。
#
# def split_lt(t: Tree, v: Any) -> tuple[Tree, Tree]:
#     """左树所有值 < v，右树所有值 >= v（通用版）。"""
#     match t:
#         case None:
#             return None, None
#         case Node(x, p, l, r, _) if x < v:
#             a, b = split_lt(r, v)
#             return node(x, p, l, a), b
#         case Node(x, p, l, r, _):
#             a, b = split_lt(l, v)
#             return a, node(x, p, b, r)


def merge(x: Tree, y: Tree) -> Tree:
    """前提：x 中所有值 <= y 中所有值。按优先级保持大根堆。"""
    match x, y:
        case None, _:
            return y
        case _, None:
            return x
        case Node(vx, px, lx, rx, _), Node(vy, py, ly, ry, _):
            if px > py:
                return node(vx, px, lx, merge(rx, y))
            return node(vy, py, merge(x, ly), ry)


# ---------- 由 split / merge 组合出的操作 ----------

def insert(t: Tree, v: Any) -> Tree:
    a, b = split_le(t, v)
    return merge(merge(a, leaf(v)), b)


def delete(t: Tree, v: Any) -> Tree:
    """删除一个等于 v 的节点；不存在则原样返回（且不复制节点）。"""
    a, rest = split_lt(t, v)      # a: < v ; rest: >= v
    mid, b = split_le(rest, v)    # mid: == v ; b: > v
    if mid is None:
        return t                  # 没找到，返回原树（结构共享）
    mid = merge(mid.l, mid.r)     # 丢弃 mid 的根
    return merge(merge(a, mid), b)


# ---------- 查询：递归，不用循环 ----------

def count_lt(t: Tree, v: Any) -> int:
    match t:
        case None:
            return 0
        case Node(x, _, l, r, _) if x < v:
            return size(l) + 1 + count_lt(r, v)
        case Node(_, _, l, _, _):
            return count_lt(l, v)


def rank(t: Tree, v: Any) -> int:
    """小于 v 的元素个数 + 1。"""
    return count_lt(t, v) + 1


def kth(t: Tree, k: int) -> Any:
    """第 k 小（1-based）。"""
    match t:
        case None:
            raise IndexError(f"kth index {k} out of range")
        case Node(x, _, l, r, _):
            ls = size(l)
            if k <= ls:
                return kth(l, k)
            if k == ls + 1:
                return x
            return kth(r, k - ls - 1)


def pre(t: Tree, v: Any) -> Any | None:
    """严格小于 v 的最大值。"""
    match t:
        case None:
            return None
        case Node(x, _, _, r, _) if x < v:
            s = pre(r, v)
            return x if s is None else s
        case Node(_, _, l, _, _):
            return pre(l, v)


def succ(t: Tree, v: Any) -> Any | None:
    """严格大于 v 的最小值。"""
    match t:
        case None:
            return None
        case Node(x, _, l, _, _) if x > v:
            s = succ(l, v)
            return x if s is None else s
        case Node(_, _, _, r, _):
            return succ(r, v)


# ---------- 遍历 ----------

def to_list(t: Tree) -> list:
    """中序遍历，纯函数。"""
    match t:
        case None:
            return []
        case Node(x, _, l, r, _):
            return to_list(l) + [x] + to_list(r)


def fold_inorder(t: Tree, f, acc):
    """中序 fold，把树当 foldable 用。"""
    match t:
        case None:
            return acc
        case Node(x, _, l, r, _):
            return fold_inorder(r, f, f(fold_inorder(l, f, acc), x))
    

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

        import random
import sys

# 洛谷 P3369 【模板】普通平衡树
# 增加递归深度以应对最坏情况
sys.setrecursionlimit(200000)


class Node:
    __slots__ = ("val", "pri", "size", "l", "r")

    def __init__(self, val: int, pri: int):
        self.val = val
        self.pri = pri
        self.size = 1
        self.l = None
        self.r = None


class FHQTreap:
    def __init__(self, seed: int = 233):
        self.root = None
        self.rng = random.Random(seed)

    def _size(self, u):
        return u.size if u is not None else 0

    def _push_up(self, u):
        u.size = self._size(u.l) + self._size(u.r) + 1

    def _new_node(self, val: int):
        return Node(val, self.rng.randint(1, 2**31 - 1))

    def split(self, u, val: int):
        """按值分裂：<= val 归入左树，> val 归入右树"""
        if u is None:
            return None, None
        if u.val <= val:
            x, y = self.split(u.r, val)
            u.r = x
            self._push_up(u)
            return u, y
        else:
            x, y = self.split(u.l, val)
            u.l = y
            self._push_up(u)
            return x, u

    def merge(self, x, y):
        """合并两棵有序树（x 中最大值 <= y 中最小值）"""
        if x is None or y is None:
            return x if y is None else y
        if x.pri > y.pri:
            x.r = self.merge(x.r, y)
            self._push_up(x)
            return x
        else:
            y.l = self.merge(x, y.l)
            self._push_up(y)
            return y

    def insert(self, val: int):
        x, y = self.split(self.root, val)
        self.root = self.merge(self.merge(x, self._new_node(val)), y)

    def delete(self, val: int):
        x, z = self.split(self.root, val)
        x, y = self.split(x, val - 1)
        if y is not None:
            y = self.merge(y.l, y.r)
        self.root = self.merge(self.merge(x, y), z)

    def rank(self, val: int) -> int:
        u = self.root
        ans = 0
        while u is not None:
            if u.val < val:
                ans += self._size(u.l) + 1
                u = u.r
            else:
                u = u.l
        return ans + 1

    def kth(self, k: int) -> int:
        u = self.root
        while u is not None:
            l_sz = self._size(u.l)
            if k <= l_sz:
                u = u.l
            elif k == l_sz + 1:
                return u.val
            else:
                k -= l_sz + 1
                u = u.r
        return 0

    def pre(self, val: int) -> int:
        u = self.root
        ans = -2147483648
        while u is not None:
            if u.val < val:
                ans = u.val
                u = u.r
            else:
                u = u.l
        return ans

    def succ(self, val: int) -> int:
        u = self.root
        ans = 2147483647
        while u is not None:
            if u.val > val:
                ans = u.val
                u = u.l
            else:
                u = u.r
        return ans


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    n = int(input_data[0])
    idx = 1
    treap = FHQTreap()
    output = []

    for _ in range(n):
        opt = int(input_data[idx])
        x = int(input_data[idx + 1])
        idx += 2

        if opt == 1:
            treap.insert(x)
        elif opt == 2:
            treap.delete(x)
        elif opt == 3:
            output.append(str(treap.rank(x)))
        elif opt == 4:
            output.append(str(treap.kth(x)))
        elif opt == 5:
            output.append(str(treap.pre(x)))
        elif opt == 6:
            output.append(str(treap.succ(x)))

    sys.stdout.write("\n".join(output) + "\n")


if __name__ == "__main__":
    main()