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;
}
真搞不懂哪儿错了。