关于在线树状数组实现平衡树

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 100001

int n, ind;
set<int> st;
map<int, int> mp, mp2;
bitset<MAXN> vis;

struct Que{
	int opt, x;
}que[MAXN];

struct BIT{
#define lowbit(x) (x & -x)
	int c[MAXN];
	void add(int x, int k){
		while (x <= ind){
			c[x] += k;
			x += lowbit(x);
		}
	}

	int query(int x){
		int res(0);
		while (x){
			res += c[x];
			x -= lowbit(x);
		}
		return res;
	}
}tr;

int get_rank(int k){
	return tr.query(mp[k]-1)+1;
}

int get_kth(int k){
	int l(1), r(ind), mid, res;
	while (l <= r){
		mid = (l+r) >> 1;
		if (tr.query(mid) < k) l = mid+1;
		else r = (res=mid)-1;
	}
	return mp2[res];
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i(1); i<=n; ++i){
		cin >> que[i].opt >> que[i].x;
		if (que[i].opt ^ 4) st.insert(que[i].x);
	}
	for (auto i: st){
		mp[i] = ++ind;
		mp2[ind] = i;
	}

	for (int i(1); i<=n; ++i){
		if (que[i].opt == 1){
			tr.add(mp[que[i].x], 1);
			vis.set(mp[que[i].x]);
		}else if (que[i].opt == 2) tr.add(mp[que[i].x], -1);
		else if (que[i].opt == 3) cout << get_rank(que[i].x) << '\n';
		else if (que[i].opt == 4) cout << get_kth(que[i].x) << '\n';
		else if (que[i].opt == 5) cout << get_kth(get_rank(que[i].x)-!vis.test(mp[que[i].x])) << '\n';
		else  cout << get_kth(get_rank(que[i].x)+vis.test(mp[que[i].x])) << '\n';
	}

	return 0;
}