RT

评测记录

#include <bits/stdc++.h>
using namespace std;
int n, opt, x;
struct node
{
    int k, pri, siz;
    node *ls, *rs;
} * root, null;
void upd(node *u)
{
    u->siz = u->ls->siz + u->rs->siz + 1;
    return;
}
node *new_node(int k)
{
    node *o = new node;
    o->k = k;
    o->pri = rand();
    o->siz = 1;
    o->ls = o->rs = &null;
    return o;
}
pair<node *, node *> sp(node *u, int k)
{
    if (u == &null)
        return make_pair(&null, &null);
    if (k < u->k)
    {
        pair<node *, node *> o = sp(u->ls, k);
        u->ls = o.second;
        upd(u);
        return make_pair(o.first, u);
    }
    pair<node *, node *> o = sp(u->rs, k);
    u->rs = o.first;
    upd(u);
    return make_pair(u, o.second);
}
node *mer(node *u, node *v)
{
    if (u == &null)
        return v;
    if (v == &null)
        return u;
    if (u->pri <= v->pri)
    {
        u->rs = mer(u->rs, v);
        upd(u);
        return u;
    }
    v->ls = mer(u, v->ls);
    upd(v);
    return v;
}
node *kth(node *u, int k)
{
    if (u == &null)
        return &null;
    if (k <= u->ls->siz)
        return kth(u->ls, k);
    else if (k == u->ls->siz + 1)
        return u;
    k -= u->ls->siz + 1;
    return kth(u->rs, k);
}
bool fnd(node *u, int k)
{
    if (u == &null)
        return false;
    if (k == u->k)
        return true;
    if (k < u->k)
        return fnd(u->ls, k);
    return fnd(u->rs, k);
}
void ins(int k)
{
    pair<node *, node *> o = sp(root, x);
    o.first = mer(o.first, new_node(k));
    root = mer(o.first, o.second);
    return;
}
void del(int k)
{
    pair<node *, node *> o = sp(root, k - 1), p = sp(o.second, k);
    delete p.first;
    root = mer(o.first, p.second);
    return;
}
int rnk(int k)
{
    pair<node *, node *> o = sp(root, k - 1);
    int s = o.first->siz + 1;
    root = mer(o.first, o.second);
    return s;
}
int main()
{
    null.siz = 0;
    root = &null;
    srand(2147483647);
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d %d", &opt, &x);
        if (opt == 1)
            ins(x);
        else if (opt == 2)
            del(x);
        else if (opt == 3)
            printf("%d\n", rnk(x));
        else if (opt == 4)
            printf("%d\n", kth(root, x)->k);
        else if (opt == 5)
        {
            pair<node *, node *> o = sp(root, x - 1);
            printf("%d\n", kth(o.first, o.first->siz)->k);
            root = mer(o.first, o.second);
        }
        else
        {
            pair<node *, node *> o = sp(root, x);
            printf("%d\n", kth(o.second, 1)->k);
            root = mer(o.first, o.second);
        }
    }
    return 0;
}