瞧一瞧,看一看,本蒟蒻才学平衡树,各位大佬帮忙看看那有问题,只有一个点对了,剩下的一半WA,一半TLE
#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;
}