7分求调(平衡树TLE)
查看原帖
7分求调(平衡树TLE)
1569747
xzxakIOI楼主2025/7/29 21:54

瞧一瞧,看一看,本蒟蒻才学平衡树,各位大佬帮忙看看那有问题,只有一个点对了,剩下的一半WA,一半TLE

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 20;
struct node{
	int son[3], fa, w, cnt, siz;
	void init(int f, int v){
		fa = f, w = v;
		cnt = siz = 1;
	}
}e[N];
int n, root, allsiz;
//定义 

void push_up(int x){
	e[x].siz = e[e[x].son[0]].siz + e[e[x].son[1]].siz + e[x].cnt;
}//辅助:回溯

void change(int x){
	int y = e[x].fa, z = e[y].fa;
	int k = (e[y].son[1] == x);
	e[y].son[k] = e[x].son[k ^ 1];
	e[e[x].son[k ^ 1]].fa = y;
	e[x].son[k ^ 1] = y; 
	e[y].fa = x;
	e[z].son[e[z].son[1] == y] = x;
	e[x].fa = z;
	push_up(y); push_up(x);
}//辅助:旋转

void splay(int x, int k){
	while(e[x].fa != k){
		int y = e[x].fa, z = e[y].fa;
		if(z != k){
			(e[y].son[0] == x) ^ (e[z].son[0] == y) ? change(x) : change(y);
		}
		change(x);
	}
	if(k == 0) root = x;
}//辅助:上移(伸展)

void find(int w){
	int x = root;
	while(e[x].son[w > e[x].w] && w != e[x].w) x = e[x].son[w > e[x].w];
	splay(x, 0);
}//转辅助:移根

void push(int w){
	int x = root, fa = 0;
	while(x && e[x].w != w){
		fa = x, x = e[x].son[w > e[x].w];
	}
	if(x){
		e[x].cnt ++;
	}
	else{
		x = ++ allsiz;
		e[fa].son[w > e[fa].w] = x;
		e[x].init(fa, w);
	}
}//操作:插入

int get_rank(int w){
	find(w);
	return e[e[root].son[0]].siz;
}//查询:数-->排名

int get_val(int k){
	int x = root;
	while(true){
		int y = e[x].son[0];
		if(e[y].siz + e[x].cnt < k){
			k -= (e[y].siz + e[x].cnt);
			x = e[x].son[1];
		}
		else{
			if(e[y].siz >= k) x = e[x].son[0];
			else break;
		}
	}
	splay(x, 0);
	return e[x].w;
}//查询:排名-->数

int get_pre(int w){
	find(w);
	int x = root;
	if(e[x].w < w) return x;
	x = e[x].son[0];
	while(e[x].son[1]) x = e[x].son[1];
	return x;
}//查询:前驱

int get_suc(int w){
	find(w);
	int x = root;
	if(e[x].w > w) return x;
	x = e[x].son[1];
	while(e[x].son[0]) x = e[x].son[0];
	return x;
}//查询:后继

void del(int w){
	int pre = get_pre(w), suc = get_suc(w);
	splay(pre, 0); splay(suc, pre);
	int del = e[suc].son[0];
	if(e[del].cnt > 1){
		e[del].cnt --;
		splay(del, 0);
	}
	else{
		e[suc].son[0] = 0;
		splay(suc, 0);
	}
}//操作:删除

signed main(){
	push(-1e9); push(1e9);
	scanf("%lld", &n);
	for(int i = 1, op, x; i <= n; i++){
		scanf("%lld%lld", &op, &x);
		if(op == 1) push(x);
		else if(op == 2) del(x);
		else if(op == 3) printf("%lld\n", get_rank(x));
		else if(op == 4) printf("%lld\n", get_val(x + 1));
		else if(op == 5) printf("%lld\n", e[get_pre(x)].w);
		else if(op == 6) printf("%lld\n", e[get_suc(x)].w);
	}
	return 0;
}
2025/7/29 21:54
加载中...