萌新刚学 OI,求助 28pts 的 Splay
查看原帖
萌新刚学 OI,求助 28pts 的 Splay
298549
SIXIANG32楼主2021/3/1 21:35
#include <iostream>
#define MAXN 100000
#define INF 0x7f7f7f7f
#define QWQ cout << "QWQ" << endl;
using namespace std;
struct  Splay {
	#define root T[0].son[1]
	struct node{
		int val,fa,siz,son[2],cnt;
	}T[MAXN+10];
	int tot;
	int LorR(int x) {
		return ((T[T[x].fa].son[0] == x)?(0):(1));
	}
	void connect(int x,int fa,int vis) {
		T[fa].son[vis] = x;
		T[x].fa = fa;
	}
	void updata(int x) {
		T[x].siz = T[T[x].son[0]].siz + T[T[x].son[1]].siz + T[x].cnt;
	}
	void rotate(int x) {
		int y = T[x].fa,r = T[T[x].fa].fa;
		int ys = LorR(x),rs = LorR(y),B = T[x].son[ys^1];
		connect(B,y,ys),connect(y,x,ys^1),connect(x,r,rs);
		updata(y),updata(x);
	}
	void splay(int x,int to) {
		to =  T[to].fa;
		while(T[x].fa != to) {
			cout << T[x].fa << ' ' << to << endl;
			if(to == T[T[x].fa].fa) rotate(x);
			else if(LorR(x) == LorR(T[x].fa)) rotate(T[x].fa),rotate(x);
			else rotate(x),rotate(x);
		}
	}
	int New(int val,int fa) {
		T[++tot].fa = fa,T[tot].val =val;
		T[tot].siz = T[tot].cnt = 1;
		return tot;
	}
	void find(int val) {
		int now = root;
		while(T[now].son[((val < T[now].val)?(0):(1))] && val != T[now].val)
			now = T[now].son[((val < T[now].val)?(0):(1))];
		splay(now,root);
	}
	void insert(int val) {
		int now = root;
		if(!now)
			root = New(val,root);
		else {
			while(233) {
				cout << now << endl;
				T[now].siz++;
				if(T[now].val == val) {
					cout << "type1" << endl;
					T[now].cnt++;
					splay(now,root);
					return ;
				}
				int next = ((val < T[now].val)?(0):(1));
				if(!T[now].son[next]) { 
					cout << "type2" << endl;
					T[now].son[next] = New(val,now);
					QWQ
					splay(tot,root);
					QWQ
					return ;
				}
				now = T[now].son[next];
			}
		} 
	}
	int low_up(int val,int f) {
		find(val);
		cout << root << ' ' << T[root].val << endl;
		if(T[root].val > val && f) return root;
		if(T[root].val < val && !f) return root;
		int now = T[root].son[f];
		while(T[now].son[f ^ 1])
			now = T[now].son[f ^ 1];
		return now;
	}
	int upper(int val) {
		return T[low_up(val,0)].val;
	}
	int lower(int val) {
		return T[low_up(val,1)].val;
	}
	int find_rank(int val) {
		find(val);
		return T[T[root].son[0]].siz;
	}
	int find_val(int rank) {
		int now = root;
		while(233) {
			if(rank <= T[T[now].son[0]].siz) now = T[now].son[0];
			else if(rank <= T[T[now].son[0]].siz + T[now].cnt) return T[now].val;
			else rank = rank - T[T[now].son[0]].siz - T[now].cnt, now = T[now].son[1];
		}
	}
	void clear(int x) {
		T[x].cnt = T[x].siz = T[x].son[0] = T[x].son[1] = T[x].val = T[x].fa = 0;
	}
	void erase(int val) {
		int pre = low_up(val,0), low = low_up(val,1);
		splay(pre,root),splay(low,pre); 
		int u = T[low].son[0];
		if(T[u].cnt > 1) {
			T[u].cnt--;
			splay(u,root);
		}
		else clear(T[low].son[0]);
		tot--;
	}
}qwq;
int main() {
	qwq.insert(INF);
	qwq.insert(-INF);
	int T,opt,val;
	cin >> T;
	while(T--) {
		cin >> opt >> val;
		if(opt == 1) qwq.insert(val);
		else if(opt == 2) qwq.erase(val);
		else if(opt == 3) cout << qwq.find_rank(val) << endl;
		else if(opt == 4) cout << qwq.find_val(val+1) << endl;
		else if(opt == 5) cout << qwq.upper(val) << endl;
		else if(opt == 6) cout << qwq.lower(val) << endl;
	}
}

下了第三个点的数据,虽说是 TLE 但是好像也错了/ch
有些东西是我调试的,请大家自行忽略
求助/kk/kk/kk

2021/3/1 21:35
加载中...