权值线段树+动态开点 RE 14pts 求调

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iomanip>
#include <string>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#define Lson tree[root].lson
#define Rson tree[root].rson
#define s tree[root].sum
using namespace std;
typedef long long ll;
template <typename T>
void read(T &x) {
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') f = -f;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	x *= f;
}
template <typename T>
void print(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x < 10) putchar(x + '0');
	else {
		print(x / 10);
		putchar(x % 10 + '0');
	}
}
const int N = 1e5 + 5, X = 1e7 + 3;
struct node {
	int lson, rson, sum;
} tree[100005 << 5];
int n, cnt, root;
map<int, int> t;
inline int max(int a, int b) {return a > b ? a : b;}
inline void pushup(int root) {
	s = tree[Lson].sum + tree[Rson].sum;
}
void update(int &root, int L, int R, int a, int k) {
	if (!root) {
		root = ++cnt;
		Lson = Rson = s = 0;
	}
	if (L == R) {
		s = max(0, s + k);
		return ;
	}
	int mid = L + R >> 1;
	if (a <= mid) update(Lson, L, mid, a, k);
	else update(Rson, mid + 1, R, a, k);
	pushup(root);
}
int query(int root, int L, int R, int l, int r) {
	if (L == R) return 0;
	if (l <= L && R <= r) return s;
	int mid = L + R >> 1, ret = 0;
	if (l <= mid) ret += query(Lson, L, mid, l, r);
	if (r > mid) ret += query(Rson, mid + 1, R, l, r);
	return ret;
}
int kth(int root, int L, int R, int k) {//主要在这
	if (L == R) return L;
	int mid = L + R >> 1, ms = tree[2 * root].sum;
	if (k <= ms) return kth(2 * root, L, mid, k);
	else return kth(2 * root + 1, mid + 1, R, k - ms);
}
int main() {
	read(n);
	while (n--) {
		int opt, x;
		read(opt);read(x);
		if (opt == 1) update(root, 1, 2 * X, x + X, 1), ++t[x];
		if (opt == 2) {
			update(root, 1, 2 * X, x + X, -1), --t[x];
			if (t[x] <= 0) t.erase(x);
		}
		if (opt == 3) print(query(root, 1, 2 * X, 1, x + X - 1) + 1);
		if (opt == 4) print(kth(root, 1, 2 * X, x + 1) - X);
		if (opt == 5) print((--t.lower_bound(x)) -> first);
		if (opt == 6) print(t.upper_bound(x) -> first);
		if (opt > 2) putchar(10);
	}
	return 0;
}