Treap求助
查看原帖
Treap求助
232838
huangkx楼主2021/6/28 14:09

AC 4个点,WA 4个点,TLE 4个点。。。
大佬帮忙看下吧:

# include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int INF = 1e7 + 5;
int sum;
int value[MAXN];
int number[MAXN];
int priority[MAXN];
int size[MAXN];
int son[MAXN][2];
int n, opt, v, R;
void pushup(int u) //计算u子树大小
{
	size[u] = size[son[u][0]] + size[son[u][1]] + number[u];
}
void rotate(int &u, bool d) //以u为根旋转,d=0左旋,d=1右旋
{
	int v = son[u][d^1];
	son[u][d^1] = son[v][d];
	son[v][d] = u;
	pushup(u);
	pushup(v);
	u = v;
}
void ins(int &u, int x) //在以u为根的子树插入值为x的节点
{
	if(u == 0){ //如果是空节点直接插入
		sum++;
		u = sum;
		value[u] = x;
		size[u] = number[u] = 1;
		priority[u] = rand();
		return;
	}
	if(value[u] == x){ //如果与当前节点重复就直接增加重复个数
		size[u]++;
		number[u]++;
		return;
	}
	int d = (x > value[u]); //判断去哪棵子树,0为左,1为右
	ins(son[u][d], x);
	if(priority[u] < priority[son[u][d]]) rotate(u, d^1); //如果优先值小于左儿子就右旋;反之亦然
	pushup(u);
}
void del(int &u, int x) //在以u为根的子树删除值为x的节点
{
	if(u == 0) ; //空节点,不管
	else if(x < value[u]) del(son[u][0], x); //小于当前,找左子树
	else if(x > value[u]) del(son[u][1], x); //大于当前,找右子树
	//以下为相等情况
	else if(!son[u][0] && !son[u][1]){ //叶子节点,直接删除
		size[u]--;
		number[u]--;
		if(number[u] == 0) u = 0;
	}else if(son[u][0] && son[u][1]){ //两个儿子都有,把大的转上来,再去相应子树删除
		int d = (priority[son[u][0]] > priority[son[u][1]]);
		rotate(u, d);
		del(son[u][d], x);
	}else{ //只有一个儿子,把它转上来,再去相应子树解决
		int d = son[u][0] ? 1 : 0;
		rotate(u, d);
		del(son[u][d], x);
	}
}
int rank(int u, int x) //在以u为根的子树查找x的排名
{
	if(u == 0) return 0;
	if(x == value[u]) return size[son[u][0]] + 1;
	if(x < value[u]) return rank(son[u][0], x);
	if(x > value[u]) return rank(son[u][0], x) + number[u] + rank(son[u][1], x);
}
int find(int u, int x) //在以u为根的子树查找排名为x的数
{
	if(u == 0) return 0;
	if(x <= size[son[u][0]]) return find(son[u][0], x);
	if(x > size[son[u][0]] + number[u]) return find(son[u][1], x-size[son[u][0]]-number[u]);
	return value[u];
}
int pre(int u, int x) //在以u为根的子树查找x的前驱
{
	if(u == 0) return -INF;
	if(x <= value[u]) return pre(son[u][0], x);
	if(x > value[u]) return max(value[u], pre(son[u][1], x));
}
int suc(int u, int x) //在以u为根的子树查找x的后继
{
	if(u == 0) return INF;
	if(x >= value[u]) return suc(son[u][1], x);
	if(x < value[u]) return min(value[u], suc(son[u][0], x));
}
int main()
{
	srand(time(NULL));
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		scanf("%d%d", &opt, &v);
		if(opt == 1) ins(R, v);
		if(opt == 2) del(R, v);
		if(opt == 3) printf("%d\n", rank(R, v));
		if(opt == 4) printf("%d\n", find(R, v));
		if(opt == 5) printf("%d\n", pre(R, v));
		if(opt == 6) printf("%d\n", suc(R, v));
	}
	return 0;
}

真搞不懂哪儿错了。

2021/6/28 14:09
加载中...