权值线段树写法 求调

#include <bits/stdc++.h>
#define il inline
namespace Fast_In {
	template <typename T> il void read(T &x) {
		x = 0; int f = 0; char ch = getchar();
		while (!isdigit(ch))f |= (ch == '-'), ch = getchar();
		while (isdigit(ch))x = x * 10 + (ch - 48), ch = getchar();
		x = f ? -x : x;
	}
	template <typename T, typename ...Args>
	il void read(T &x, Args& ...args) {read(x), read(args...);}
} using namespace Fast_In;
namespace Fast_Out {
	template <typename T> il void write(T x, char c = '\n') {
		if (x) {
			if (x < 0)x = -x, putchar('-');
			char a[30]; short l;
			for (l = 0; x; x /= 10)a[l ++] = x % 10 ^ 48;
			for (l --; l >= 0; l --)putchar(a[l]);
		} else putchar('0');
		putchar(c);
	}
	template <typename T, typename ...Args>
	il void write(T x, Args ...args) {write(x), write(args...);}
} using namespace Fast_Out;
using namespace std;

const int N = 100005;
int tree[N << 2], n, m, op[N], a[N], b[N];
il int ls(int u) {return u << 1;}
il int rs(int u) {return u << 1;}
il void pushup(int u) {tree[u] = tree[ls(u)] + tree[rs(u)];}
void update(int u, int l, int r, int x, int k) {
	if (l == r) {
		tree[u] += k;
		return ;
	}
	int mid = (l + r) >> 1;
	if (x <= mid)update(ls(u), l, mid, x, k);
	else update(rs(u), mid + 1, r, x, k);
	pushup(u);
}
int query_rnk(int u, int l, int r, int x, int y) {
	if (x <= l && r <= y) return tree[u];
	int mid = (l + r) >> 1, ret = 0;
	if (x <= mid)ret += query_rnk(ls(u), l, mid, x, y);
	if (mid < y) ret += query_rnk(rs(u), mid + 1, r, x, y);
	return ret;
}
int query_val(int u, int l, int r, int x) {
	if (l == r) return l;
	int mid = (l + r) >> 1;
	if (x <= tree[ls(u)]) return query_val(ls(u), l, mid, x);
	else return query_val(rs(u), mid + 1, r, x - tree[ls(u)]);
}
signed main() {
	read(n);
	for (int i = 1; i <= n; i ++) {
		read(op[i], a[i]);
		if (op[i] != 4) {
			m ++;
			b[m] = a[i];
		}
	}
	sort(b + 1, b + m + 1);
	m = unique(b + 1, b + m + 1) - b - 1;
	for (int i = 1, id, rk; i <= n; i ++) {
		if (op[i] != 4)id = lower_bound(b + 1, b + m + 1, a[i]) - b;
		if (op[i] == 1)update(1, 1, m, id, 1);  //加上一次
		if (op[i] == 2)update(1, 1, m, id, -1); //减去一次
		if (op[i] == 3) {
			if (id > 1)write(query_rnk(1, 1, m, 1, id - 1) + 1);
			else write(1);
		} 
		if (op[i] == 4)write(b[query_val(1, 1, m, a[i])]);
		if (op[i] == 5) {
			rk = query_rnk(1, 1, m, 1, id - 1);
			write(b[query_val(1, 1, m, rk)]);
		}
		if (op[i] == 6) {
			rk = query_rnk(1, 1, m, 1, id) + 1;
			write(b[query_val(1, 1, m, rk)]);
		}
	}
	return 0;
}