tags

树状数组 数据结构

中文题面

题目描述

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

1. 插入一个数 $x$。
2. 删除一个数 $x$（若有多个相同的数，应只删除一个）。
3. 定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。
4. 查询数据结构中排名为 $x$ 的数。
5. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
6. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。

对于操作 3,5,6，不保证当前数据结构中存在数 $x$。

输入格式

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

输出格式

对于操作 $3,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\%$ 的数据，$1\le n\le 10^5$，$|x|\le 10^7$

思路

总结这题需要实现的功能基本就是实时更改数组并能 找到数组中第 $k$ 大的数，这可以用树状数组来解决，实现与平衡树相同的功能，由于 $|x|<10^7$，我们可以开 $2\times 10^7$ 的空间，每个下标对应的值表示当前值在数组内有几个，对其进行更新，查询排名时二分查找即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N (int)2e7 + 1000
#define lowbit(x) (x & -x)int x, n, t, l, r, op;
int tree[N];
void add(int x, int k) {while (x <= n) {tree[x] += k;x += lowbit(x);}
}
int sum(int x) {int ans = 0;while (x) {ans += tree[x];x -= lowbit(x);}return ans;
}map<int, int> mp;
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);// 注意根据数据量调整N的大小n = 2e7 + 1;cin >> t;while (t--) {cin >> op >> x;if (op == 1) add(x + 1e7 + 1, 1);else if (op == 2) add(x + 1e7 + 1, -1);else if (op == 3) cout << sum(x + 1e7) + 1 << '\n';else if (op == 4) {l = 1, r = n;int ans = 0;while (l <= r) {int mid = l + r >> 1;if (sum(mid - 1) + 1 > x) r = mid - 1;else ans = mid - 1e7 - 1, l = mid + 1;}cout << ans << '\n';} else if (op == 5) {int now = sum(x + 1e7);int l = 1, r = x + 1e7;int ans = 0;while (l <= r) {int mid = l + r >> 1;if (sum(mid) == now) ans = mid - 1e7 - 1, r = mid - 1;else l = mid + 1;}cout << ans << '\n';} else {int now = sum(x + 1e7 + 1);int l = x + 1e7 + 2, r = n;int ans = 0;while (l <= r) {int mid = l + r >> 1;if (sum(mid) == now) l = mid + 1;else ans = mid - 1e7 - 1, r = mid - 1;}cout << ans << '\n';}}return 0;
}