堆#

堆用来解决一些需要快速排序，并且每次只关心排序后最值的问题．

C++ STL 中的优先队列就是用堆实现的．

堆是特殊的二叉树，有一个最重要的性质：对于堆中的任何一个节点，都保证其子节点的值严格大于父节点．

例如下面一张图就符合堆的性质

堆的操作#

节点添加#

设需要在上图中添加一个元素 4，我们可以这么做：

首先，我们先将要添加的节点放到最下一层最右边的叶子之后．如果最下一层已满，就新增一层．

而后，尝试让新的节点和其父节点交换位置．在这个例子中，显然，4 是比 6 要小的，为了保证堆的性质，我们要让 4 和 6 换个位置．

显然，3 是比 4 要小的，已经满足了堆的性质，这一次添加操作就此结束．

堆的删除#

堆支持删除最顶上的一个节点．

为了对上面一张图的顶点（即值为 3 的点）进行删除，我们可以这样做：

首先，把这个点和最后一个点交换位置

再把最后一个点删掉

然后，由于这个图不满足堆的定义，所以我们从他的子节点中选择一个最小的，和根节点交换，作为新的根节点．

之后一直交换，直到其所有子节点都大于父节点，或没有子节点为止．

查询最小值#

这个最简单，此时堆顶的元素最小，没有比它更小的了．

复杂度分析#

节点添加操作平均是 $O(\log n)$ 的，但最坏 $O(n)$ ．

查询最小值 $O(1)$ ．

删除操作平均是 $O(\log n)$ 的，但最坏 $O(n)$ ．

题目：P3378 【模板】堆

题目描述#

给定一个数列，初始为空，请支持下面三种操作：

给定一个整数 $x$ ，请将 $x$ 加入到数列中．
输出数列中最小的数．
删除数列中最小的数（如果有多个数最小，只删除 $1$ 个）．

输入格式#

第一行是一个整数，表示操作的次数 $n$ ．接下来 $n$ 行，每行表示一次操作．每行首先有一个整数 $op$ 表示操作类型．

若 $op = 1$ ，则后面有一个整数 $x$ ，表示要将 $x$ 加入数列．
若 $op = 2$ ，则表示要求输出数列中的最小数．
若 $op = 3$ ，则表示删除数列中的最小数．如果有多个数最小，只删除 $1$ 个．

输出格式#

对于每个操作 $2$ ，输出一行一个整数表示答案．

数据范围#

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^6$ ， $1 \leq x \lt 2^{31}$ ， $op \in \{1, 2, 3\}$ ．

标程#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define fa(x) (x / 2)
4
#define lson(x) (2 * x)
5
#define rson(x) (2 * x + 1)
6

7
const int N = 1e6 + 100;
8
const int root = 1;
9

10
int n;
11

12
class Heap
13
{
14
private:
15
    int size = 0;
16
    int a[N];
17

18
public:
19
    Heap()
20
    {
21
        memset(a, 0x3f, sizeof(a));
22
    }
23
    void push(int x)
24
    {
25
        a[++size] = x;
26
        int now = size;
27
        while (now > root)
28
        {
29
            if (a[now] < a[fa(now)])
30
            {
31
                swap(a[now], a[fa(now)]);
32
                now = fa(now);
33
            }
34
            else
35
                break;
36
        }
37
    }
38
    int query()
39
    {
40
        return a[root];
41
    }
42
    void remove()
43
    {
44
        int now = root;
45
        a[root] = a[size];
46
        size--;
47
        while (lson(now) <= size)
48
        {
49
            int minn = lson(now);
50
            if (rson(now) <= size && a[rson(now)] < a[minn])
51
                minn = rson(now);
52
            if (a[now] > a[minn])
53
            {
54
                swap(a[now], a[minn]);
55
                now = minn;
56
            }
57
            else
58
                break;
59
        }
60
    }
61
};
62

63
signed main()
64
{
65
    cin >> n;
66
    Heap heap;
67
    for (int i = 1; i <= n; i++)
68
    {
69
        int op;
70
        cin >> op;
71
        if (op == 1)
72
        {
73
            int x;
74
            cin >> x;
75
            heap.push(x);
76
        }
77
        if (op == 2)
78
            cout << heap.query() << endl;
79
        if (op == 3)
80
            heap.remove();
81
    }
82
    return 0;
83
}

二叉搜索树#

题目：P3369【模板】普通平衡树

题目描述#

您需要动态地维护一个可重集合 $M$ ，并且提供以下操作：

向 $M$ 中插入一个数 $x$ ．
从 $M$ 中删除一个数 $x$ （若有多个相同的数，应只删除一个）．
查询 $M$ 中有多少个数比 $x$ 小，并且将得到的答案加一．
查询如果将 $M$ 从小到大排列后，排名位于第 $x$ 位的数．
查询 $M$ 中 $x$ 的前驱（前驱定义为小于 $x$ ，且最大的数）．
查询 $M$ 中 $x$ 的后继（后继定义为大于 $x$ ，且最小的数）．

对于操作 $3,5,6$ ，不保证当前可重集中存在数 $x$ ．

对于操作 $5,6$ ，保证答案一定存在．

输入格式#

第一行为 $n$ ，表示操作的个数，下面 $n$ 行每行有两个数 $\text{opt}$ 和 $x$ ， $\text{opt}$ 表示操作的序号（ $1 \leq \text{opt} \leq 6$ ）．

输出格式#

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

数据范围#

对于 $100\%$ 的数据， $1\le n \le 10^5$ ， $|x| \le 10^7$ ．

二叉搜索树是一种特殊的树，其特点为：对于一个节点，其左子树上的节点总是小于父节点，而其右子树上的节点总是大于父节点．

例如下面一张图就符合二叉搜索树的性质

对于每一个节点，我们需要记录一些信息：

v：该节点的值．
num：为了让二叉搜索树能够存储重复的数据，我们将数值相同的节点合并．num 表示树中共有 num 个数值为 v 的值，即该节点是由 num 个节点合并而来的．
lson：该节点的左子节点．
rson：该节点的右子节点．
size：以本节点为根的子树中一共有多少个数（此处不是节点，是因为每一个节点可能储存多个相同的数），包括根节点．

1
struct Node {
2
  int v;
3
  int num;
4
  int size;
5
  int lson;
6
  int rson;
7

8
  Node() : v(0), num(0), size(0), lson(0), rson(0) {}
9

10
  Node(int v, int num = 1) {
11
    init(v, num);
12
  }
13

14
  void init(int v, int num) {
15
    this->v = v;
16
    this->num = num;
17
    this->size = num;
18
  }
19

20
  // 左节点
21
  int lsize();
22
  // 右节点
23
  int rsize();
24
  // 计算大小
25
  void push_up() {
26
    size = lsize() + rsize() + num;
27
  }
28
} node[N];
29

30
int Node::lsize() {
31
  return node[lson].size;
32
}
33
int Node::rsize() {
34
  return node[rson].size;
35
}

定义一个类用来存放操作函数：

1
class Tree {
2
public:
3
  // 当前根节点
4
  int ROOT = 0;
5
  // 当前树中节点数量
6
  int tot = 0;
7
  queue<int> free_node;
8
};

插入#

插入很简单，只需要从根节点向下遍历一遍，找到最适合的位置．

对于一个节点 $k$ ，要在以该节点为根的子树中插入一个元素 $x$ ，有两种情况

若节点 $k$ 是空的，则将 $x$ 放在 $k$ 的位置．
若节点 $k$ $k$ 非空，则
- $x = k$ ，将节点 $k$ 的 num 值增加即可．
- $x\lt k$ ，可以转化为在节点为 $k_{lson}$ 为根的子树下插入元素 $x$ ．
- $x \gt k$ ，可以转化为在节点为 $k_{rson}$ 为根的子树下插入元素 $x$ ．

最后，在统计 size 时，可以使用类似于线段树的 pushup 方法，将左右子树的 size 相加即可．

时间复杂度为 $O(h)$ ， $h$ 为高度，最坏 $O(n)$

由于有删除有新增，所以需要一个函数来动态管理内存．

1
class Tree {
2
public:
3
  // 当前空的节点
4
  // 会在删除时，将删除后空出来的位置记录
5
  queue<int> free_node;
6
  // 获得下一个空位
7
  int next_node_pos() {
8
    if (!free_node.empty()) {
9
      // 有空位
10
      int u = free_node.front();
11
      free_node.pop();
12
      return u;
13
    }
14
    // 开辟新的位子
15
    return ++tot;
16
  }
17
};

以下代码使用递归进行插入：

1
void insert(int x, int& now) { // now是int&，&不能忘记
2
  if (now == 0)
3
  {
4
    // 当前节点是空的
5
    // 申请新的空间
6
    now = next_node_pos();
7
    // 登记挂载到父节点上
8
    node[now] = Node(x);
9
  }
10
  else {
11
    if (node[now].v == x) {
12
      node[now].num++;
13
    }
14
    else if (node[now].v < x) {
15
      insert(x, node[now].rson);
16
    }
17
    else {
18
      insert(x, node[now].lson);
19
    }
20
  }
21
  node[now].push_up();
22
}

查询排名#

依旧的，进行一次搜索．

如果你想要查询 $x$ 在树中是排第几位的，那么只需要算出比 $x$ 小的数有几个，而后，将结果加一，即为排名．

特殊的，如果 $x$ 不存在，则假想 $x$ 存在，即定义 $x$ 的排名为比 $x$ 小的数的个数加一．

为了统计比 $x$ 小的数有几个，如果你当前遍历到节点 $k$ ，那么有以下三种情况：

$x \lt k$ ，比 $x$ 小的数一定都在 $k$ 的左子树上，可以舍弃右子树，继续遍历左子树．
$x=k$ ，其实和 $x \lt k$ 的情况是一样的．
$x \gt k$ ，此时左子树中的一定都是比 $x$ 小的，右子树中有部分．将左子树和 $k$ 计入答案，继续遍历右子树．

1
int rank(int x) {
2
  int now = ROOT;
3
  int ans = 0;
4
  while (now) {
5
    if (x <= node[now].v) {
6
      now = node[now].lson;
7
    }
8
    else if (x > node[now].v) {
9
      ans += node[now].lsize() + node[now].num;
10
      now = node[now].rson;
11
    }
12
  }
13
  return ans + 1;
14
}

查询第几大#

为了查询第 $x$ 大的数，如果你当前遍历到节点 $k$ ，若定义 $k$ 的左子树大小为 $k_{lsize}$ ，那么有以下三种情况：

$x \le k_{lsize}$ ，即第 $x$ 大的数在 $k$ 的左子树，只需要继续遍历左子树即可．
$k_{lsize} \gt x \le k_{lsize} + k_{num}$ ，即第 $x$ 大的数就是 $k$
否则，第 $x$ 大的数在 $k$ 的右子树，将 $x$ 减去左子树和 $k$ 点的数量后，继续遍历右子树．

1
int kth(int x) {
2
  int now = ROOT;
3
  while (now) {
4
    if (node[now].lsize() >= x) {
5
      now = node[now].lson;
6
    }
7
    else if (node[now].lsize() + node[now].num >= x) {
8
      return node[now].v;
9
    }
10
    else {
11
      x -= node[now].lsize() + node[now].num;
12
      now = node[now].rson;
13
    }
14
  }
15
  return -1; // 不会抵达
16
}

查询前驱/后继#

计算前驱（即最大的比 $x$ 小的数），可以得知 $x$ 的排名后，再将排名减一后用 kth 查询即可．

计算后继（即最小的比 $x$ 大的数），显然，后继一定比原数至少大 1，可以通过得知 $x+1$ 的排名后，通过这个排名来用 kth 查询．

1
int pre(int x) {
2
  return kth(rank(x) - 1);
3
}
4
int succ(int x) {
5
  return kth(rank(x + 1));
6
}

删除#

为了删除 $x$ ，如果你当前遍历到节点 $k$ ，那么有以下三种情况：

$x \lt k$ ， $x$ 一定在 $k$ 的左子树上，可以继续遍历左子树．
$x \gt k$ ， $x$ 一定在 $k$ 的右子树上，可以继续遍历右子树．
$x=k$ $x = k$
- 如果 $k_{num} \ne 1$ ，即还有多个此种数字，那么直接让 $k_{num}-1$ 即可．
- 否则，就需要删除这个节点
  - 如果节点 $k$ 没有子节点，直接删
  - 如果节点 $k$ 只有左子节点或右子节点，那么将其子节点覆盖父节点．
  - 如果 $k$ 有两个子节点，那么，寻找 $k$ 的前驱或后继，将其覆盖节点 $k$ （注意，一定是覆盖而非替换，因为如果替换就会破坏平衡树的大小规则）．可以证明，节点 $k$ 的前驱和后继分别在 $k$ 的左子树和右子树上．并且， $k$ 的前驱和后继必然大于原来 $k$ 的左子树上的节点且小于原来 $k$ 右子树上的节点．

1
void remove(int x, int& now) {
2
  if (!now) return;
3
  if (x < node[now].v) {
4
    remove(x, node[now].lson);
5
  }
6
  else if (x > node[now].v) {
7
    remove(x, node[now].rson);
8
  }
9
  else {
10
    // 找到要删除的节点
11
    if (node[now].num > 1) {
12
      // 节点有大于1个元素，直接删
13
      node[now].num--;
14
    }
15
    else if (node[now].lson == 0 && node[now].rson == 0) {
16
      // 节点左右都没有节点，直接删
17
      // 由于删除之后这个位置会空缺，所以记录
18
      free_node.push(now);
19
      // 在父节点登记
20
      now = 0;
21
    }
22
    else if (node[now].lson == 0) {
23
      // 节点没有左节点
24
      // 由于删除之后这个位置会空缺，所以记录
25
      free_node.push(now);
26
      // 在父节点登记
27
      now = node[now].rson;
28
    }
29
    else if (node[now].rson == 0) {
30
      // 节点没有右节点，和左节点相同
31
      free_node.push(now);
32
      now = node[now].lson;
33
    }
34
    else {
35
      // 节点又有左节点，又有右节点
36
      // 获取后继的值
37
      int suc = node[now].rson;
38
      // 获取值对应的下标
39
      while (node[suc].lson) suc = node[suc].lson;
40
      // 覆盖
41
      node[now].v = node[suc].v;
42
      node[now].num = node[suc].num;
43
      // 防止删不掉
44
      node[suc].num = 1;
45
      // 在右节点范围进行删除
46
      remove(node[suc].v, node[now].rson);
47
    }
48
  }
49
  // 由于对节点进行了改动，需要重新计算大小
50
  // 一定要避免对节点0的push_up
51
  if (now) node[now].push_up();
52
}

时间复杂度#

每一项操作的时间复杂度都是 $O(h)$ ，其中 $h$ 是深度，共有 $n$ 次操作，综合最坏 $O(n^2)$ ．

标程#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int N = 1e5 + 100;
5
int n;
6

7
struct Node {
8
  int v;
9
  int num;
10
  int size;
11
  int lson;
12
  int rson;
13

14
  Node() : v(0), num(0), size(0), lson(0), rson(0) {}
15

16
  Node(int v, int num = 1) {
17
    init(v, num);
18
  }
19

20
  void init(int v, int num) {
21
    this->v = v;
22
    this->num = num;
23
    this->size = num;
24
  }
25

26
  int lsize();
27
  int rsize();
28
  void push_up() {
29
    size = lsize() + rsize() + num;
30
  }
31
} node[N];
32

33
int Node::lsize() {
34
  return node[lson].size;
35
}
36
int Node::rsize() {
37
  return node[rson].size;
38
}
39

40
class Tree {
41
public:
42
  int ROOT = 0;
43
  int tot = 0;
44
  queue<int> free_node;
45

46
  int next_node_pos() {
47
    if (!free_node.empty()) {
48
      int u = free_node.front();
49
      free_node.pop();
50
      return u;
51
    }
52
    return ++tot;
53
  }
54

55
  void insert(int x, int& now) {
56
    if (now == 0)
57
    {
58
      now = next_node_pos();
59
      node[now] = Node(x);
60
    }
61
    else {
62
      if (node[now].v == x) {
63
        node[now].num++;
64
      }
65
      else if (node[now].v < x) {
66
        insert(x, node[now].rson);
67
      }
68
      else {
69
        insert(x, node[now].lson);
70
      }
71
    }
72
    node[now].push_up();
73
  }
74

75
  int rank(int x) {
76
    int now = ROOT;
77
    int ans = 0;
78
    while (now) {
79
      if (x <= node[now].v) {
80
        now = node[now].lson;
81
      }
82
      else if (x > node[now].v) {
83
        ans += node[now].lsize() + node[now].num;
84
        now = node[now].rson;
85
      }
86
    }
87
    return ans + 1;
88
  }
89

90
  int kth(int x) {
91
    int now = ROOT;
92
    while (now) {
93
      if (node[now].lsize() >= x) {
94
        now = node[now].lson;
95
      }
96
      else if (node[now].lsize() + node[now].num >= x) {
97
        return node[now].v;
98
      }
99
      else {
100
        x -= node[now].lsize() + node[now].num;
101
        now = node[now].rson;
102
      }
103
    }
104
    return -1;
105
  }
106

107
  int pre(int x) {
108
    return kth(rank(x) - 1);
109
  }
110
  int succ(int x) {
111
    return kth(rank(x + 1));
112
  }
113

114
  void remove(int x, int& now) {
115
    if (!now) return;
116
    if (x < node[now].v) {
117
      remove(x, node[now].lson);
118
    }
119
    else if (x > node[now].v) {
120
      remove(x, node[now].rson);
121
    }
122
    else {
123
      if (node[now].num > 1) {
124
        node[now].num--;
125
      }
126
      else if (node[now].lson == 0 && node[now].rson == 0) {
127
        free_node.push(now);
128
        now = 0;
129
      }
130
      else if (node[now].lson == 0) {
131
        free_node.push(now);
132
        now = node[now].rson;
133
      }
134
      else if (node[now].rson == 0) {
135
        free_node.push(now);
136
        now = node[now].lson;
137
      }
138
      else {
139
        int suc = node[now].rson;
140
        while (node[suc].lson) suc = node[suc].lson;
141
        node[now].v = node[suc].v;
142
        node[now].num = node[suc].num;
143
        node[suc].num = 1;
144
        remove(node[suc].v, node[now].rson);
145
      }
146
    }
147
    if (now) node[now].push_up();
148
  }
149
};
150

151
int main() {
152
  cin >> n;
153
  Tree tree;
154
  for (int i = 1; i <= n; i++) {
155
    int opt, x;
156
    cin >> opt >> x;
157
    if (opt == 1) {
158
      tree.insert(x, tree.ROOT);
159
    }
160
    if (opt == 2) {
161
      tree.remove(x, tree.ROOT);
162
    }
163
    if (opt == 3) {
164
      cout << tree.rank(x) << endl;
165
    }
166
    if (opt == 4) {
167
      cout << tree.kth(x) << endl;
168
    }
169
    if (opt == 5) {
170
      cout << tree.pre(x) << endl;
171
    }
172
    if (opt == 6) {
173
      cout << tree.succ(x) << endl;
174
    }
175
  }
176
  return 0;
177
}

二叉平衡树#

显然最坏 $O(n^2)$ 的时间复杂度无法通过，所以需要一些优化．

替罪羊树#

很显然，之所以会有最坏 $O(n^2)$ ，是因为失衡，使其退化成了接近链的形式．

因此，只需要在插入之后进行一次重构，就可以解决这个问题．

究竟在何时重构呢？在这里要引入一个常数 $\alpha \in (0.5, 1)$ （常取 0.75），当左子树节点数 $siz_1$ 和右子树节点数 $siz_2$ 和当前字数总节点数 $siz_0$ 满足 $max(siz_1, siz_2) > \alpha siz_0$ 时，需要重构．

为了实现，我们需要定义：

1
struct Node {
2
  int v;
3
  int num;
4
  int size;
5
  // 用于计算当前字数中有多少个节点
6
  int tot; // [!code highlight]
7
  int lson;
8
  int rson;
9

10
  Node() : v(0), num(0), size(0), lson(0), rson(0), tot(0) {}
11

12
  Node(int v, int num = 1) {
13
    init(v, num);
14
  }
15

16
  void init(int v, int num) {
17
    this->v = v;
18
    this->num = num;
19
    this->size = num;
20
    this->tot = 1;
21
  }
22

23
  int lsize();
24
  int rsize();
25
  int ltot();
26
  int rtot();
27
  void push_up() {
28
    size = lsize() + rsize() + num;
29
    // 注意比对size和tot之间更新的差异
30
    tot = ltot() + rtot() + 1; // [!code highlight]
31
  }
32
} node[N];
33

34
int Node::lsize() {
35
  return node[lson].size;
36
}
37
int Node::rsize() {
38
  return node[rson].size;
39
}
40
int Node::ltot() {
41
  return node[lson].tot;
42
}
43
int Node::rtot() {
44
  return node[rson].tot;
45
}

在插入时，我们需要在回溯时判断这个节点是否平衡，如果不平衡，将其记录．

每一次插入，只有一个节点，即最上面的一个不平衡的节点需要被视为重构的根节点．

1
int insert(int x, int& now) {
2
  // 记录重构的节点
3
  // 此处的null是一个常数，代表没有节点需要重构
4
  // 可以将其定义为-1或INT_MIN
5
  int ref_node = null; // [!code highlight]
6
  if (now == 0)
7
  {
8
    now = next_node_pos();
9
    node[now] = Node(x);
10
  }
11
  else {
12
    if (node[now].v == x) {
13
      node[now].num++;
14
    }
15
    else if (node[now].v < x) {
16
      ref_node = insert(x, node[now].rson);
17
    }
18
    else {
19
      ref_node = insert(x, node[now].lson);
20
    }
21
  }
22
  node[now].push_up();
23
  // 如果该节点不平衡，就记录该节点．
24
  // [!code highlight:3]
25
  if (max(node[now].ltot(), node[now].rtot()) > node[now].tot * ALPHA)
26
    ref_node = now;
27
  return ref_node;
28
}

在 main 函数中处理 insert 的返回值．

1
if (opt == 1) {
2
  int ref_node = tree.insert(x, tree.ROOT);
3
  if (ref_node != null) {
4
    tree.rebuild(ref_node);
5
  }
6
}

当需要重构时，调用重构函数．重构主要需要完成以下几件事：

获取中序遍历结果．
删除子树中的所有节点．
用像线段树一样的方法去重建树．

1
public:
2
  void rebuild(int root) {
3
    // 获取中序遍历结果，并删除节点
4
    // 这里pair的第一个参数表示值（v），第二个参数表示数量（num）
5
    vector<pair<int, int> > list;
6
    flatten(node[root].lson, list);
7
    list.push_back({ node[root].v, node[root].num });
8
    flatten(node[root].rson, list);
9
    // 重建树
10
    build(root, list, 0, list.size() - 1);
11
  }
12

13
private:
14
  // 展平操作
15
  // 将以root为根的子树中序遍历并完全删除，结果储存到list中
16
  // 这里list是引用类型，&不要忘了加
17
  void flatten(int root, vector<pair<int, int> >& list) {
18
    // 防止根节点是空的
19
    if (root == 0) return;
20
    // 展平左节点
21
    flatten(node[root].lson, list);
22
    // 加入自身
23
    list.push_back({ node[root].v, node[root].num });
24
    // 展平右节点
25
    flatten(node[root].rson, list);
26
    // 删除自身
27
    free_node.push(root);
28
  }
29
  // 使用list中[l,r]的部分以root为根节点重建
30
  // 此处的list一定要是引用类型，因为如果是值传递，频繁的拷贝vector会导致复杂度急剧上升
31
  void build(int root, const vector<pair<int, int> >& list, int l, int r) {
32
    // 获取root应为的值和数量，即list[mid]
33
    int mid = (l + r) / 2;
34
    node[root] = Node(list[mid].first, list[mid].second);
35

36
    if (l <= mid - 1)
37
    {
38
      // 构建左子树
39
      node[root].lson = next_node_pos();
40
      build(node[root].lson, list, l, mid - 1);
41
    }
42
    if (mid + 1 <= r)
43
    {
44
      // 构建右子树
45
      node[root].rson = next_node_pos();
46
      build(node[root].rson, list, mid + 1, r);
47
    }
48

49
    // 由于构建操作更改了节点，所以需要push_up
50
    node[root].push_up();
51
  }

时间复杂度#

由于使用了重构，所以单次操作时间复杂度是均摊 $O(\log n)$ 的，总时间复杂度 $O(n\log n)$

标程#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int N = 1e5 + 100;
5
const double ALPHA = 0.75;
6
const int null = INT_MIN;
7
int n;
8

9
struct Node {
10
  int v;
11
  int num;
12
  int size;
13
  int tot;
14
  int lson;
15
  int rson;
16

17
  Node() : v(0), num(0), size(0), lson(0), rson(0), tot(0) {}
18

19
  Node(int v, int num = 1) {
20
    init(v, num);
21
  }
22

23
  void init(int v, int num) {
24
    this->v = v;
25
    this->num = num;
26
    this->size = num;
27
    this->tot = 1;
28
  }
29

30
  int lsize();
31
  int rsize();
32
  int ltot();
33
  int rtot();
34
  void push_up() {
35
    size = lsize() + rsize() + num;
36
    tot = ltot() + rtot() + 1;
37
  }
38
} node[N];
39

40
int Node::lsize() {
41
  return node[lson].size;
42
}
43
int Node::rsize() {
44
  return node[rson].size;
45
}
46
int Node::ltot() {
47
  return node[lson].tot;
48
}
49
int Node::rtot() {
50
  return node[rson].tot;
51
}
52

53
class Tree {
54
public:
55
  int ROOT = 0;
56
  int tot = 0;
57
  queue<int> free_node;
58

59
  int next_node_pos() {
60
    if (!free_node.empty()) {
61
      int u = free_node.front();
62
      free_node.pop();
63
      return u;
64
    }
65
    return ++tot;
66
  }
67

68
  int insert(int x, int& now) {
69
    int ref_node = null;
70
    if (now == 0)
71
    {
72
      now = next_node_pos();
73
      node[now] = Node(x);
74
    }
75
    else {
76
      if (node[now].v == x) {
77
        node[now].num++;
78
      }
79
      else if (node[now].v < x) {
80
        ref_node = insert(x, node[now].rson);
81
      }
82
      else {
83
        ref_node = insert(x, node[now].lson);
84
      }
85
    }
86
    node[now].push_up();
87
    if (max(node[now].ltot(), node[now].rtot()) > node[now].tot * ALPHA) {
88
      ref_node = now;
89
    }
90
    return ref_node;
91
  }
92

93
  int rank(int x) {
94
    int now = ROOT;
95
    int ans = 0;
96
    while (now) {
97
      if (x <= node[now].v) {
98
        now = node[now].lson;
99
      }
100
      else if (x > node[now].v) {
101
        ans += node[now].lsize() + node[now].num;
102
        now = node[now].rson;
103
      }
104
    }
105
    return ans + 1;
106
  }
107

108
  int kth(int x) {
109
    int now = ROOT;
110
    while (now) {
111
      if (node[now].lsize() >= x) {
112
        now = node[now].lson;
113
      }
114
      else if (node[now].lsize() + node[now].num >= x) {
115
        return node[now].v;
116
      }
117
      else {
118
        x -= node[now].lsize() + node[now].num;
119
        now = node[now].rson;
120
      }
121
    }
122
    return -1;
123
  }
124

125
  int pre(int x) {
126
    return kth(rank(x) - 1);
127
  }
128
  int succ(int x) {
129
    return kth(rank(x + 1));
130
  }
131

132
  void remove(int x, int& now) {
133
    if (!now) return;
134
    if (x < node[now].v) {
135
      remove(x, node[now].lson);
136
    }
137
    else if (x > node[now].v) {
138
      remove(x, node[now].rson);
139
    }
140
    else {
141
      if (node[now].num > 1) {
142
        node[now].num--;
143
      }
144
      else if (node[now].lson == 0 && node[now].rson == 0) {
145
        free_node.push(now);
146
        now = 0;
147
      }
148
      else if (node[now].lson == 0) {
149
        free_node.push(now);
150
        now = node[now].rson;
151
      }
152
      else if (node[now].rson == 0) {
153
        free_node.push(now);
154
        now = node[now].lson;
155
      }
156
      else {
157
        int suc = node[now].rson;
158
        while (node[suc].lson) suc = node[suc].lson;
159
        node[now].v = node[suc].v;
160
        node[now].num = node[suc].num;
161
        node[suc].num = 1;
162
        remove(node[suc].v, node[now].rson);
163
      }
164
    }
165
    if (now) node[now].push_up();
166
  }
167

168
  void rebuild(int root) {
169
    vector<pair<int, int> > list;
170
    flatten(node[root].lson, list);
171
    list.push_back({ node[root].v, node[root].num });
172
    flatten(node[root].rson, list);
173
    build(root, list, 0, list.size() - 1);
174
  }
175
private:
176
  void flatten(int root, vector<pair<int, int> >& list) {
177
    if (root == 0) return;
178
    flatten(node[root].lson, list);
179
    list.push_back({ node[root].v, node[root].num });
180
    flatten(node[root].rson, list);
181
    free_node.push(root);
182
  }
183
  void build(int root, const vector<pair<int, int> >& list, int l, int r) {
184
    int mid = (l + r) / 2;
185
    node[root] = Node(list[mid].first, list[mid].second);
186

187
    if (l <= mid - 1)
188
    {
189
      node[root].lson = next_node_pos();
190
      build(node[root].lson, list, l, mid - 1);
191
    }
192
    if (mid + 1 <= r)
193
    {
194
      node[root].rson = next_node_pos();
195
      build(node[root].rson, list, mid + 1, r);
196
    }
197

198
    node[root].push_up();
199
  }
200
};
201

202
int main() {
203
  ios::sync_with_stdio(false);
204
  cin.tie(nullptr);
205
  cin >> n;
206
  Tree tree;
207
  for (int i = 1; i <= n; i++) {
208
    int opt, x;
209
    cin >> opt >> x;
210
    if (opt == 1) {
211
      int ref_node = tree.insert(x, tree.ROOT);
212
      if (ref_node != null) {
213
        tree.rebuild(ref_node);
214
      }
215
    }
216
    if (opt == 2) {
217
      tree.remove(x, tree.ROOT);
218
    }
219
    if (opt == 3) {
220
      cout << tree.rank(x) << endl;
221
    }
222
    if (opt == 4) {
223
      cout << tree.kth(x) << endl;
224
    }
225
    if (opt == 5) {
226
      cout << tree.pre(x) << endl;
227
    }
228
    if (opt == 6) {
229
      cout << tree.succ(x) << endl;
230
    }
231
  }
232
  return 0;
233
}

音乐

音乐

堆#

堆的操作#

节点添加#

堆的删除#

查询最小值#

复杂度分析#

题目描述#

输入格式#

输出格式#

数据范围#

标程#

二叉搜索树#

题目描述#

输入格式#

输出格式#

数据范围#

插入#

查询排名#

查询第几大#

查询前驱/后继#

删除#

时间复杂度#

标程#

二叉平衡树#

替罪羊树#

时间复杂度#

标程#

文章分享

音乐

堆与平衡树

堆#

堆的操作#

节点添加#

堆的删除#

查询最小值#

复杂度分析#

题目描述#

输入格式#

输出格式#

数据范围#

标程#

二叉搜索树#

题目描述#

输入格式#

输出格式#

数据范围#

插入#

查询排名#

查询第几大#

查询前驱/后继#

删除#

时间复杂度#

标程#

二叉平衡树#

替罪羊树#

时间复杂度#

标程#

文章分享