结构体Treap求助
查看原帖
结构体Treap求助
759274
Stevehim楼主2023/3/28 21:58

RT,不知道哪错了

#include <bits/stdc++.h>
#define maxn 1000010
#define inf 1145141919
using namespace std;
int opt, x;
int a[maxn];
int n, m;
int last = 0;

template<typename T>inline void read(T &ff) {
	T rr = 1;
	ff = 0;
	register char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-')
			rr = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		ff = (ff << 1) + (ff << 3) + (ch ^ 48);
		ch = getchar();
	}
	ff *= rr;
}

struct Treap {//treap模板,有需要可以copy
	int tot, rt;
	struct node {
		int val, ch[2], rd, cnt, sz;
		void Init(int Val) {
			val = Val, rd = rand() % 233;
			sz = cnt = 1;
			ch[1] = ch[0] = 0;
		}
	} tr[maxn];
	void pushup(int nod) {
		tr[nod].sz = tr[tr[nod].ch[0]].sz + tr[tr[nod].ch[1]].sz + tr[nod].cnt;
	}
	void rotate(int &nod, int d) {
		int k = tr[nod].ch[d];
		tr[nod].ch[d] = tr[k].ch[d ^ 1];
		tr[k].ch[d ^ 1] = nod;
		pushup(nod);
		pushup(k);
		nod = k;
	}
	void ins(int &nod, int val) {
		if (!nod) {
			nod = ++ tot;
			tr[nod].Init(val);
		} else {
			tr[nod].sz ++;
			if (tr[nod].val == val) {
				tr[nod].cnt ++;
				return;
			}
			int d = val > tr[nod].val;
			ins(tr[nod].ch[d], val);
			if (tr[nod].rd > tr[tr[nod].ch[d]].rd)
				rotate(nod, d);
		}
	}
	void del(int &nod, int val) {
		if (!nod)
			return;
		if (tr[nod].val == val) {
			if (tr[nod].cnt > 1) {
				tr[nod].cnt --, tr[nod].sz --;
				return;
			}
			int d = tr[tr[nod].ch[0]].rd > tr[tr[nod].ch[1]].rd;
			if (!tr[nod].ch[1] || !tr[nod].ch[0])
				nod = tr[nod].ch[1] + tr[nod].ch[0];
			else
				rotate(nod, d), del(nod, val);
		} else
			tr[nod].sz --, del(tr[nod].ch[tr[nod].val < val], val);
//		pushup(nod);
	}
	int _rank(int nod, int val) {
		if (!nod)
			return 1;
		if (tr[nod].val == val)
			return tr[tr[nod].ch[0]].sz + 1;
		if (tr[nod].val < val)
			return tr[tr[nod].ch[0]].sz + tr[nod].cnt + _rank(tr[nod].ch[1], x);
		if (tr[nod].val > val)
			return _rank(tr[nod].ch[0], x);
	}
	int find(int nod, int val) {
		if (!nod)
			return 0;
		if (tr[tr[nod].ch[0]].sz >= val)
			return find(tr[nod].ch[0], val);
		else if (tr[tr[nod].ch[0]].sz + tr[nod].cnt < val)
			return find(tr[nod].ch[1], val - tr[nod].cnt - tr[tr[nod].ch[0]].sz);
		else
			return tr[nod].val; //都等于了,对吧
	}
	int pre(int nod, int val) {
		if (!nod)
			return -inf;
		if (tr[nod].val > val)
			return pre(tr[nod].ch[0], val);
		else
			return max(tr[nod].val, pre(tr[nod].ch[1], val));
	}
	int suc(int nod, int val) {
		if (!nod)
			return inf;
		if (tr[nod].val < val)
			return suc(tr[nod].ch[1], val);
		else
			return min(tr[nod].val, suc(tr[nod].ch[0], val));
	}
	int Get_Min(int nod) {
		if (!nod)
			return inf;
		return min(tr[nod].val, Get_Min(tr[nod].ch[0]));
	}
} tr;

int main() {
	read(n);
	for (register int i = 1; i <= n; i++) {
		read(opt);
		read(x);
//		x ^= last;
		if (opt == 1)
			tr.ins(tr.rt, x);
		if (opt == 2) {
			tr.del(tr.rt, x);
		} else if (opt == 3) {
			cout << tr._rank(tr.rt, x) << endl;
//			ans ^= 1ll * last;
		} else if (opt == 4) {
			cout << tr.find(tr.rt, x) << endl;
//			ans ^= 1ll * last;
		} else if (opt == 5) {
			cout << tr.pre(tr.rt, x) << endl;
//			ans ^= 1ll * last;
		} else if (opt == 6) {
			cout << tr.suc(tr.rt, x) << endl;
		}
	}
//	cout << ans;
	return 0;
}
2023/3/28 21:58
加载中...