萌新求助UB
查看原帖
萌新求助UB
361308
Stinger楼主2021/1/31 20:43

真的是萌新,真的是蒟蒻。

洛谷IDE和本地不一样。

#include <cstdio>
#include <cstdlib>

inline int max(const int x, const int y) {return x > y ? x : y;}
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Node {
	int ch[2], r, v, cnt, s;
} t[200005];

int tot = 1, p, root = 1;
inline void maintain(const int O) {t[O].s = t[t[O].ch[0]].s + t[t[O].ch[1]].s + t[O].cnt;}

inline void rotate(int& O, const int d) {
	int k(t[O].ch[d ^ 1]);
	t[O].ch[d ^ 1] = t[k].ch[d], t[k].ch[d] = O;
	maintain(O), maintain(k);
	O = k;
}
void insert(int& O, const int x) {//option 1
	++ t[O].s;
	if (t[O].v == x) {++ t[O].cnt; return;}
	int d(t[O].v < x);
	if (t[O].ch[d]) {
		insert(t[O].ch[d], x);
		if (t[t[O].ch[d]].r > t[O].r) rotate(O, d ^ 1);
	}
	else {
		t[O].ch[d] = ++ tot, t[tot].s = t[tot].cnt = 1, t[tot].v = x, t[tot].r = rand();
		if (t[t[O].ch[d]].r > t[O].r) rotate(O, d ^ 1);
	}
}

void remove(int& O, const int x) {//option 2
	-- t[O].s;
	if (t[O].v == x) {
		-- t[O].cnt;
		if (t[O].cnt) return;
		if (!t[O].ch[0]) O = t[O].ch[1];
		else if (!t[O].ch[1]) O = t[O].ch[0];
		else {
			int d(t[t[O].ch[0]].r < t[t[O].ch[1]].r);
			rotate(O, d), remove(t[O].ch[d], x);
		}
	} else remove(t[O].ch[t[O].v < x], x);
}

int rank(int O, const int x) {//option 3
	if (O == 0) return 0;
	if (x < t[O].v) return rank(t[O].ch[0], x);
	else return t[t[O].ch[0]].s + 1 + rank(t[O].ch[1], x);
}
int rank2(int O, const int x) {//option 4
	if (x <= t[t[O].ch[0]].s) return rank2(t[O].ch[0], x);
	if (x <= t[t[O].ch[0]].s + t[O].cnt) return t[O].v;
	return rank2(t[O].ch[1], x - t[t[O].ch[0]].s - t[O].cnt);
}

bool find(int O, const int x) {
	if (O == 0) return 0;
	if (t[O].v == x) return 1;
	return find(t[O].ch[t[O].v < x], x);
}

void Pre(int O, const int x) {// option 5
	if (O == 0) return;
	if (t[O].v < x) {
		p = t[O].v;
		Pre(t[O].ch[1], x);
	}
	else Pre(t[O].ch[0], x);
}
void Nxt(int O, const int x) {// option 6
	if (O == 0) return;
	if (t[O].v > x) {
		p = t[O].v;
		Nxt(t[O].ch[0], x);
	}
	else Nxt(t[O].ch[1], x);
}

int main() {
	int n;
	bool mark(0);
	scanf("%d", &n);
	while (n --) {
		int opt, x;
		scanf("%d%d", &opt, &x);
		if (opt == 1) {
			if (mark) insert(root, x);
			else t[1].v = x, t[1].s = t[1].cnt = 1, t[1].r = rand();
			mark = true;
		}
		else if (!mark) continue;
		else if (opt == 2) {if (find(root, x)) remove(root, x);}
		else if (opt == 3) printf("%d\n", rank(root, x));
		else if (opt == 4) printf("%d\n", rank2(root, x));
		else if (opt == 5) printf("%d\n", (Pre(root, x), p));
		else if (opt == 6) printf("%d\n", (Nxt(root, x), p));
	}
}
2021/1/31 20:43
加载中...