rt

WA的点根据提示是在某不知名操作上给出的都是0

TLE未知

#include <vector>
#include <iostream>
using namespace std;
struct node
{
    int val;
    int l = 0, r = 0;
    int size = 1, fact = 1;
    int cnt = 1;
} p[100005];
int n, root = 1, cnt = 1;
inline bool imbalance(int now)
{
    if (0.7 * p[now].size >= p[now].fact)
        return true;
    if (max(p[p[now].l].size, p[p[now].r].size) >= 0.75 * p[now].size)
        return true;
    return false;
}
vector<int> v;
void ldr(int now)
{
    if (!now)
        return;
    ldr(p[now].l);
    if (p[now].cnt)
        v.push_back(now);
    ldr(p[now].r);
}
void lift(int l, int r, int &now)
{
    if (l == r)
    {
        now = v[l];
        p[now].size = p[now].fact = p[now].cnt;
        p[now].l = p[now].r = 0;
        return;
    }
    int mid = (r - l) / 2 + l;
    /*while (mid > l && p[v[mid - 1]].val == p[v[mid]].val)
        mid--;*/
    now = v[mid];
    if (l < mid)
        lift(l, mid - 1, p[now].l);
    else
        p[now].l = 0;
    lift(mid + 1, r, p[now].r);
    p[now].size = p[p[now].l].size + p[p[now].r].size + p[now].cnt;
    p[now].fact = p[p[now].l].fact + p[p[now].r].fact + p[now].cnt;
}
void rebuild(int &now)
{
    v.clear();
    ldr(now);
    if (v.empty())
        now = 0;
    else
        lift(0, v.size() - 1, now);
}
void update(int now, int end)
{
    if (!now)
        return;
    if (p[now].val > p[end].val)
        update(p[now].l, end);
    else
        update(p[now].r, end);
    p[now].size = p[p[now].l].size + p[p[now].r].size + p[now].cnt;
    p[now].fact = p[p[now].l].fact + p[p[now].r].fact + p[now].cnt;
}
void check(int &now, int end)
{
    if (now == end)
        return;
    if (imbalance(now))
    {
        rebuild(now);
        update(root, now);
        return;
    }
    if (p[now].val < p[end].val)
        check(p[now].l, end);
    else
        check(p[now].r, end);
}
void insert(int &now, int inum)
{
    if (!now)
    {
        now = cnt++;
        p[now].val = inum;
        check(root, now);
        return;
    }
    p[now].size++;
    p[now].fact++;
    if (inum < p[now].val)
        insert(p[now].l, inum);
    else if (inum == p[now].val)
    {
        p[now].cnt++;
        check(root, now);
    }
    else
        insert(p[now].r, inum);
}
void del(int now, int dnum)
{
    p[now].fact--;
    if (p[now].val == dnum && p[now].cnt)
    {
        p[now].cnt--;
        check(root, now);
        return;
    }
    if (dnum < p[now].val)
        del(p[now].l, dnum);
    else
        del(p[now].r, dnum);
}
int getrank(int num)
{
    int rank = 1, now = root;
    while (now)
    {
        if (p[now].val < num)
        {
            rank += p[now].cnt + p[p[now].l].fact;
            now = p[now].r;
        }
        else
            now = p[now].l;
    }
    return rank;
}
int getnum(int rank)
{
    int now = root;
    while (now)
    {
        if (p[now].cnt && p[p[now].l].fact + p[now].cnt == rank)
            break;
        if (p[p[now].l].fact < rank)
        {
            rank -= p[p[now].l].fact + p[now].cnt;
            now = p[now].r;
        }
        else
            now = p[now].l;
    }
    return p[now].val;
}
int main()
{
    p[0].fact = p[0].size = p[0].cnt = 0;
    ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    freopen("out.out", "w", stdout);
#endif
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int opt, x;
        cin >> opt >> x;
        if (opt == 1)
        {
            if (cnt == 1 || root == 0)
            {
                root = cnt++;
                p[root].val = x;
            }
            else
                insert(root, x);
        }
        else if (opt == 2)
            del(root, x);
        else if (opt == 3)
            cout << getrank(x) << endl;
        else if (opt == 4)
            cout << getnum(x) << endl;
        else if (opt == 5)
            cout << getnum(getrank(x) - 1) << endl;
        else if (opt == 6)
            cout << getnum(getrank(x + 1)) << endl;
    }
    return 0;
}