Treap 和 Splay 死活学不会，真的太难了，只好使用线段树来解决平衡树问题了。

以洛谷 P3369 来引出这种做法。很不错的是，这道题允许离线。

权值线段树的思想是，叶节点保存的是当前节点的 $l$（由于是叶节点，故也可以认为是 $r$）的出现次数。如此可以在 $O(\log n)$ 的复杂度快速求出区间内的数字个数，以实现此题所要求的 kth 问题。

但是很明显，这道题不能直接按照 $x$ 的真实值进行线段树建树（$|x|\leq 10^7）$，故我们需要进行离散化。此处需注意，由于题目说明对于操作 $3,5,6$ 不保证当前可重集中存在数 $x$，故并非只有操作 1 的 $x$ 需要进行离散化，我们需要对除了操作 4 以外的所有 $x$ 均进行离散化。

那我们就可以知道了，由于需要离散化，这题必须得离线完成。但是如果考虑动态开点的线段树，貌似可以实现在线。但是我不会，挖个坑，以后来补。

对于每一个操作（定义 $\text{Hash}(val)$ 为 $val$ 的哈希值，定义 $\text{Real}(val)$ 为 $val$ 的真实值，故 $\text{Real}(\text{Hash}(val))=val$）：

1. 直接让区间 $[\text{Hash}(x),\text{Hash}(x)]$ 加一

2. 直接让区间 $[\text{Hash}(x),\text{Hash}(x)]$ 减一

3. 输出 $[1,\text{Hash}(x) - 1]$（即 $[1, \text{Hash}(x))$）的区间和 +1

4. 此处需要利用权值线段树的优点了。

   对于当前 $(id,l,r)$ 的节点，若 $\text{ls}(id)$ 的总和小于 $k$，则目标答案一定在左子树上，走左子树。反之，则一定在右子树上，走右子树。注意，因为左子树不走，当前 $k$ 需要减去左子树大小。

   若 $l=r$ 则说明已经找到了，返回 $l$（当然，你也可以返回 $r$，他们是相等的。）

   最后答案应当为 $\text{Real}(l)$。

5. 先查询 $[1,\text{Hash(x)}]$ 的区间和 $k$。但是不能直接输出排位为 $k-1$ 的区间和，因为由于是可重集，排位为 $k-1$ 与排位为 $k$ 的值可能相同，故我们还需要查询 $\text{Hash}(x)$ 的值的个数 $\text{sameNum}$。输出结果应当为排位为 $k-\text{sameNum}$ 的值。

6. 先查询 $[1,\text{Hash(x)}]$ 的区间和 $k$，用操作 3 实现。随后利用操作 4 输出排位为 $k + 1$ 的值。

   实际上操作 5、6 所得的 $k$ 是最后一个 $x$ 的排位。

以上。

不懂看代码：

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <unordered_map>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair

const int maxn = 1e5 + 10;

int n;
pii opt[maxn];
int cnt = 0;
unordered_map<int, int> hashval;
unordered_map<int, int> realval;

int tree[maxn * 4];
int ls(int id) { return id << 1; }
int rs(int id) { return id << 1 | 1; }
void pushup(int id) {
	tree[id] = tree[ls(id)] + tree[rs(id)];
}

void add(int id, int l, int r, int x, int v) {
	if (l == r) {
		tree[id] += v;
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) {
		add(ls(id), l, mid, x, v);
	}
	if (x > mid) {
		add(rs(id), mid + 1, r, x, v);
	}
	pushup(id);
}
int query(int id, int l, int r, int x, int y) {
	if (l > r || x > y || y < l || x > r)
		return 0;
	if (x <= l && r <= y) {
		return tree[id];
	}
	int mid = (l + r) >> 1;
	int ans = 0;
	if (x <= mid) {
		ans += query(ls(id), l, mid, x, y);
	}
	if (y > mid) {
		ans += query(rs(id), mid + 1, r, x, y);
	}
	return ans;
}
int kth(int id, int l, int r, int k) {
	if (l == r)
		return l;
	int mid = (l + r) >> 1;
	if (k <= tree[ls(id)]) {
		return kth(ls(id), l, mid, k);
	} else {
		return kth(rs(id), mid + 1, r, k - tree[ls(id)]);
	}
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> opt[i].first >> opt[i].second;
	}

	// 离散化
	vector<pii> nums; // first=val, second=i
	for (int i = 1; i <= n; i++) {
		if (opt[i].first != 4) {
			nums.push_back(mp(opt[i].second, i));
		}
	}
	sort(nums.begin(), nums.end());
	for (auto k : nums) {
		if (!hashval.count(k.first)) {
			hashval[k.first] = ++cnt;
			realval[cnt] = k.first;
		}
	}

	// 无需初始化权值线段树 因为初始均为0次
	for (int i = 1; i <= n; i++) {
		int op = opt[i].first, x = opt[i].second;
		if (op == 1) {
			add(1, 1, cnt, hashval[x], 1);
		}
		if (op == 2) {
			add(1, 1, cnt, hashval[x], -1);
		}
		if (op == 3) {
			cout << query(1, 1, cnt, 1, hashval[x] - 1) + 1 << endl;
		}
		if (op == 4) {
			cout << realval[kth(1, 1, cnt, x)] << endl;
		}
		if (op == 5) {
			int k = query(1, 1, cnt, 1, hashval[x]);
			int sameNum = query(1, 1, cnt, hashval[x], hashval[x]);
			cout << realval[kth(1, 1, cnt, k - sameNum)] << endl;
		}
		if (op == 6) {
			int k = query(1, 1, cnt, 1, hashval[x]);
			cout << realval[kth(1, 1, cnt, k + 1)] << endl;
		}
	}
	return 0;
}

注意到，此为单点修改，区间查询，可以用树状数组替换线段树优化一下，常数小一点：

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <unordered_map>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair

const int maxn = 1e5 + 10;

int n;
pii opt[maxn];
int cnt = 0;
unordered_map<int, int> hashval;
unordered_map<int, int> realval;

int tree[maxn * 4];

int lowbit(int x) { return x & (-x); }
void add(int x, int v) {
	for (int i = x; i <= cnt; i += lowbit(i)) {
		tree[i] += v;
	}
}
int query(int x) {
	int ans = 0;
	for (int i = x; i > 0; i -= lowbit(i)) {
		ans += tree[i];
	}
	return ans;
}
int kth(int k) {
	int pos = 0;
	int step = 1;
	while ((step << 1) <= cnt) {
		step <<= 1;
	}
	for (int d = step; d; d >>= 1) {
		if (pos + d <= cnt && tree[pos + d] < k) {
			pos += d;
			k -= tree[pos];
		}
	}
	return pos + 1;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> opt[i].first >> opt[i].second;
	}

	vector<pii> nums;
	for (int i = 1; i <= n; i++) {
		if (opt[i].first != 4) {
			nums.push_back(mp(opt[i].second, i));
		}
	}
	sort(nums.begin(), nums.end());
	for (auto k : nums) {
		if (!hashval.count(k.first)) {
			hashval[k.first] = ++cnt;
			realval[cnt] = k.first;
		}
	}

	for (int i = 1; i <= n; i++) {
		int op = opt[i].first, x = opt[i].second;
		if (op == 1) {
			add(hashval[x], 1);
		}
		if (op == 2) {
			add(hashval[x], -1);
		}
		if (op == 3) {
			cout << query(hashval[x] - 1) + 1 << endl;
		}
		if (op == 4) {
			cout << realval[kth(x)] << endl;
		}
		if (op == 5) {
			int k = query(hashval[x]);
			int sameNum = query(hashval[x]) - query(hashval[x] - 1);
			cout << realval[kth(k - sameNum)] << endl;
		}
		if (op == 6) {
			int k = query(hashval[x]);
			cout << realval[kth(k + 1)] << endl;
		}
	}
	return 0;
}

额，其实用处不并不大，只快了几毫秒。总运行时间还是 std 的三倍左右，但是仍然轻松可以通过此题。