交上去WA#4,MLE#5-10,下载了第4个点,结果本地测是对的,已调崩溃,求助大佬
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 100000;
const ll N = maxn * 2 + 10;
struct nde{
ll val, rnd, siz, l, r;
};
struct treap{
ll cnt, rt;
nde a[N];
void clr() {
cnt = 0;
rt = 0;
}
void pushup(ll x) {
a[x].siz = a[a[x].l].siz + a[a[x].r].siz + 1;
}
ll new_nde(ll k) {
++cnt;
a[cnt].val = k;
a[cnt].rnd = rand();
a[cnt].siz = 1;
a[cnt].l = 0;
a[cnt].r = 0;
return cnt;
}
void lrtt(ll &x) {
ll k = a[x].r;
a[x].r = a[k].l;
a[k].l = x;
pushup(x);
pushup(k);
x = k;
}
void rrtt(ll &x) {
ll k = a[x].l;
a[x].l = a[k].r;
a[k].r = x;
pushup(x);
pushup(k);
x = k;
}
void insrt(ll &x, ll k) {
if (x == 0) {
x = new_nde(k);
return;
}
if (k < a[x].val) {
insrt(a[x].l, k);
pushup(x);
if (a[x].rnd < a[a[x].l].rnd) {
rrtt(x);
}
}
else {
insrt(a[x].r, k);
pushup(x);
if (a[x].rnd < a[a[x].r].rnd) {
lrtt(x);
}
}
}
void remve(ll &x, ll k) {
if (a[x].val == k) {
if (a[x].l == 0 && a[x].r == 0) {
x = 0;
}
else if (a[x].l > 0) {
x = a[x].l;
}
else if(a[x].r > 0) {
x = a[x].r;
}
else {
if (a[a[x].l].rnd < a[a[x].r].rnd) {
lrtt(x);
remve(a[x].l, k);
}
else {
rrtt(x);
remve(a[x].r, k);
}
}
return;
}
if (a[x].val > k) {
remve(a[x].l, k);
}
else {
remve(a[x].r, k);
}
pushup(x);
}
ll get_rank(ll x, ll k) {
if (x == 0) {
return 0;
}
if (k <= a[x].val) {
return get_rank(a[x].l, k);
}
else {
return (get_rank(a[x].r, k) + a[a[x].l].siz + 1);
}
}
ll get_val(ll x, ll k) {
if (k <= a[a[x].l].siz) {
return get_val(a[x].l, k);
}
else if (k == a[a[x].l].siz + 1) {
return a[x].val;
}
else {
return get_val(a[x].r, k - a[a[x].l].siz - 1);
}
}
ll get_pre(ll x, ll k) {
if (x == 0) {
return 0;
}
if (k <= a[x].val) {
return get_pre(a[x].l, k);
}
else {
ll y = get_pre(a[x].r, k);
if (y == 0) {
return a[x].val;
}
else {
return y;
}
}
}
ll get_suf(ll x, ll k) {
if (x == 0) {
return 0;
}
if (k >= a[x].val) {
return get_suf(a[x].r, k);
}
else {
ll y = get_suf(a[x].l, k);
if (y == 0) {
return a[x].val;
}
else {
return y;
}
}
}
}st;
ll n, m;
int main() {
scanf("%lld", &n);
st.clr();
for (ll i = 1; i <= n; ++i) {
ll opt, x, ans;
scanf("%lld%lld", &opt, &x);
if (opt == 1) {
st.insrt(st.rt, x);
}
else if (opt == 2) {
st.remve(st.rt, x);
}
else if (opt == 3) {
ans = st.get_rank(st.rt, x) + 1;
printf("%lld\n", ans);
}
else if (opt == 4) {
ans = st.get_val(st.rt, x);
printf("%lld\n", ans);
}
else if (opt == 5) {
ans = st.get_pre(st.rt, x);
printf("%lld\n", ans);
}
else if (opt == 6) {
ans = st.get_suf(st.rt, x);
printf("%lld\n", ans);
}
}
return 0;
}