44pts求调
查看原帖
44pts求调
817681
HZHDCM楼主2024/8/5 22:21

不会调,求dalao帮帮

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct Treap {
	int l, r;
	int key, pri; //插入的数,优先级
	int size;
} t[N];
int cnt, root, n;
void New(int x) {
	t[++cnt].size = 1;
	t[cnt].l = t[cnt].r = 0;
	t[cnt].key = x;
	t[cnt].pri = rand();
}
void push_up(int u) {
	t[u].size = t[t[u].l].size + t[t[u].r].size + 1;
}
void rotate(int &o, int d) { //d=0右旋,d=1左旋
	int k;
	if (d) {
		k = t[o].r;
		t[o].r = t[k].l;
		t[k].l = o;
		t[k].size = t[o].size;
		t[o].size=t[o].size-(t[t[o].r].size+1);
	} else {
		k = t[o].l;
		t[o].l = t[k].r;
		t[k].r = o;
		t[k].size = t[o].size;
		t[o].size=t[o].size-(t[t[o].l].size+1);
	}
	push_up(o);
	o = k;
}
void Insert(int &u, int x) {
	if (!u) {
		New(x);
		u = cnt;
		return ;
	}
	t[u].size++;
	if (x >= t[u].key)Insert(t[u].r, x);
	else Insert(t[u].l, x);
	if (t[u].l && t[u].pri > t[t[u].l].pri)rotate(u, 0);
	if (t[u].r && t[u].pri > t[t[u].r].pri)rotate(u, 1);
	push_up(u);
}
void Del(int &u, int x) { //删
	t[u].size--;
	if (t[u].key == x) {
		if (!t[u].l && !t[u].r) {
			u = 0;
			return ;
		}
		if (!t[u].l || !t[u].r) {
			u = t[u].l + t[u].r;
			return ;
		}
		if (t[t[u].l].pri < t[t[u].r].pri) {
			rotate(u, 0);
			Del(t[u].r, x);
			return ;
		} else {
			rotate(u, 1);
			Del(t[u].l, x);
			return ;
		}
		if (t[u].key >= x)Del(t[u].l, x);
		else Del(t[u].r, x);
		push_up(u);
	}
}
int Rank(int u, int x) {
	if (!u)return 0;
	if (x > t[u].key)return t[t[u].l].size + 1 + Rank(t[u].r, x);
	return Rank(t[u].l, x);
}
int kth(int u, int k) {
	if (k == t[t[u].l].size + 1)return t[u].key;
	if (k > t[t[u].l].size + 1)return kth(t[u].r, k - t[t[u].l].size - 1);
	if (k <= t[t[u].l].size) return kth(t[u].l, k);
}
int Find_pri(int u, int x) {
	if (!u)return 0;
	if (t[u].key >= x)return Find_pri(t[u].l, x);
	int val = Find_pri(t[u].r, x);
	if (!val)return t[u].key;
	return val;
}
int Find_nxt(int u, int x) {
	if (!u)return 0;
	if (t[u].key <= x)return Find_nxt(t[u].r, x);
	int val = Find_nxt(t[u].l, x);
	if (!val)return t[u].key;
	return val;
}
int main() {
	srand(time(NULL));
	cin >> n;
	while (n--) {
		int opt, x;
		cin >> opt >> x;
		switch (opt) {
			case 1:
				Insert(root, x);
				break;
			case 2:
				Del(root, x);
				break;
			case 3:
				cout << Rank(root, x) + 1 << endl;
				break;
			case 4:
				cout << kth(root, x) << endl;
				break;
			case 5:
				cout << Find_pri(root, x) << endl;
				break;
			case 6:
				cout << Find_nxt(root, x) << endl;
				break;
		}
	}
	return 0;
}
2024/8/5 22:21
加载中...