// Treap
#include <bits/stdc++.h>
using namespace std;

const unsigned int MAXN = 1e5 + 10;

class treap
{
private:
  struct treapNode
  {
    int value;
    unsigned int priority;
    unsigned int cnt;
    unsigned int size;
    unsigned int lc;
    unsigned int rc;
#define v(k) t[k].value
#define p(k) t[k].priority
#define c(k) t[k].cnt
#define s(k) t[k].size
#define lc(k) t[k].lc
#define rc(k) t[k].rc
  };
  treapNode t[MAXN];
  unsigned int pos = 0, root = 0;
  void update(const int unsigned k) { s(k) = s(lc(k)) + s(rc(k)) + c(k); }
  inline void zig(unsigned int &k)
  {
    int y = lc(k);
    lc(k) = rc(y);
    rc(y) = k;
    s(y) = s(k);
    update(k);
    k = y;
  }
  inline void zag(unsigned int &k)
  {
    int y = rc(k);
    rc(k) = lc(y);
    lc(y) = k;
    s(y) = s(k);
    update(k);
    k = y;
  }
  inline void insert_basic(unsigned int &k, const int val)
  {
    if (!k)
    {
      k = ++pos;
      v(k) = val;
      p(k) = rand();
      c(k) = s(k) = 1;
      lc(k) = rc(k) = 0;
    }
    else
    {
      s(k)++;
      if (v(k) == val)
        c(k)++;
      else if (val < v(k))
      {
        insert_basic(lc(k), val);
        if (p(lc(k)) < p(k))
          zig(k);
      }
      else
      {
        insert_basic(rc(k), val);
        if (p(rc(k)) < p(k))
          zag(k);
      }
    }
  }
  inline void erase_basic(unsigned int &k, const int val)
  {
    if (v(k) == val)
    {
      if (c(k) > 1)
      {
        c(k)--;
        s(k)--;
      }
      else if (!lc(k) || !rc(k))
        k = lc(k) + rc(k);
      else if (p(lc(k)) < p(rc(k)))
        zig(k), erase_basic(k, val);
      else
        erase_basic(rc(k), val);
    }
    else
    {
      s(k)--;
      if (val < v(k))
        erase_basic(lc(k), val);
      else
        erase_basic(rc(k), val);
    }
  }

public:
  inline void insert(const int val)
  {
    insert_basic(root, val);
  }
  inline void erase(const int val)
  {
    erase_basic(root, val);
  }
  inline int pre(const int val)
  {
    unsigned int x = root;
    int res = INT_MIN;
    while (x)
    {
      if (v(x) <= val)
        res = v(x), x = rc(x);
      else
        x = lc(x);
    }
    return res;
  }
  inline int post(const int val)
  {
    unsigned int x = root;
    int res = INT_MAX;
    while (x)
    {
      if (v(x) >= val)
        res = v(x), x = lc(x);
      else
        x = rc(x);
    }
    return res;
  }
  inline unsigned int rank(const int val)
  {
    unsigned int x = root;
    unsigned int res = 0;
    while (x)
    {
      if (val == v(x))
        return res + (s(lc(x))) + 1;
      else if (val < v(x))
        x = lc(x);
      else
        res += s(lc(x)) + c(x), x = rc(x);
    }
    return res;
  }
  inline int kth(unsigned int k)
  {
    unsigned int x = root;
    while (x)
    {
      if (s(lc(x)) < k && s(lc(x)) + c(x) >= k)
        return v(x);
      else if (s(lc(x)) >= k)
        x = lc(x);
      else
        k -= s(lc(x)) + c(x), x = rc(x);
    }
    return INT_MIN;
  }
} t;
int n, opt, x;

int main()
{
#ifndef ONLINE_JUDGE
  freopen(".input.txt", "r", stdin);
  // freopen(".output.txt", "w", stdout);
#endif
  scanf("%d", &n);
  while (n--)
  {
    scanf("%d%d", &opt, &x);
    if (opt == 1)
      t.insert(x);
    else if (opt == 2)
      t.erase(x);
    else if (opt == 3)
      printf("%d\n", t.rank(x));
    else if (opt == 4)
      printf("%d\n", t.kth(x));
    else if (opt == 5)
      printf("%d\n", t.pre(x));
    else
      printf("%d\n", t.post(x));
  }
  return 0;
}

Splay就没问题

//Splay
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;

struct Splay
{
  int rt, tot, fa[MAXN], ch[MAXN][2], val[MAXN], cnt[MAXN], sz[MAXN];
  void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; }
  bool get(int x) { return x == ch[fa[x]][1]; }
  void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0; }
  void rotate(int x)
  {
    int y = fa[x], z = fa[y], chk = get(x);
    ch[y][chk] = ch[x][chk ^ 1];
    if (ch[x][chk ^ 1])
      fa[ch[x][chk ^ 1]] = y;
    ch[x][chk ^ 1] = y;
    fa[y] = x;
    fa[x] = z;
    if (z)
      ch[z][y == ch[z][1]] = x;
    maintain(y);
    maintain(x);
  }

  void splay(int x)
  {
    for (int f = fa[x]; f = fa[x], f; rotate(x))
      if (fa[f])
        rotate(get(x) == get(f) ? f : x);
    rt = x;
  }

  void ins(int k)
  {
    if (!rt)
    {
      val[++tot] = k;
      cnt[tot]++;
      rt = tot;
      maintain(rt);
      return;
    }
    int cur = rt, f = 0;
    while (1)
    {
      if (val[cur] == k)
      {
        cnt[cur]++;
        maintain(cur);
        maintain(f);
        splay(cur);
        break;
      }
      f = cur;
      cur = ch[cur][val[cur] < k];
      if (!cur)
      {
        val[++tot] = k;
        cnt[tot]++;
        fa[tot] = f;
        ch[f][val[f] < k] = tot;
        maintain(tot);
        maintain(f);
        splay(tot);
        break;
      }
    }
  }

  int rk(int k)
  {
    int res = 0, cur = rt;
    while (1)
    {
      if (k < val[cur])
        cur = ch[cur][0];
      else
      {
        res += sz[ch[cur][0]];
        if (!cur)
          return res + 1;
        if (k == val[cur])
        {
          splay(cur);
          return res + 1;
        }
        res += cnt[cur];
        cur = ch[cur][1];
      }
    }
  }

  int kth(int k)
  {
    int cur = rt;
    while (1)
    {
      if (ch[cur][0] && k <= sz[ch[cur][0]])
        cur = ch[cur][0];
      else
      {
        k -= cnt[cur] + sz[ch[cur][0]];
        if (k <= 0)
        {
          splay(cur);
          return val[cur];
        }
        cur = ch[cur][1];
      }
    }
  }

  int pre()
  {
    int cur = ch[rt][0];
    if (!cur)
      return cur;
    while (ch[cur][1])
      cur = ch[cur][1];
    splay(cur);
    return cur;
  }

  int nxt()
  {
    int cur = ch[rt][1];
    if (!cur)
      return cur;
    while (ch[cur][0])
      cur = ch[cur][0];
    splay(cur);
    return cur;
  }

  void del(int k)
  {
    rk(k);
    if (cnt[rt] > 1)
    {
      cnt[rt]--;
      maintain(rt);
      return;
    }
    if (!ch[rt][0] && !ch[rt][1])
    {
      clear(rt);
      rt = 0;
      return;
    }
    if (!ch[rt][0])
    {
      int cur = rt;
      rt = ch[rt][1];
      fa[rt] = 0;
      clear(cur);
      return;
    }
    if (!ch[rt][1])
    {
      int cur = rt;
      rt = ch[rt][0];
      fa[rt] = 0;
      clear(cur);
      return;
    }
    int cur = rt;
    int x = pre();
    fa[ch[cur][1]] = x;
    ch[x][1] = ch[cur][1];
    clear(cur);
    maintain(rt);
  }
} tree;

int main()
{
  int n, opt, x;
  for (scanf("%d", &n); n; --n)
  {
    scanf("%d%d", &opt, &x);
    if (opt == 1)
      tree.ins(x);
    else if (opt == 2)
      tree.del(x);
    else if (opt == 3)
      printf("%d\n", tree.rk(x));
    else if (opt == 4)
      printf("%d\n", tree.kth(x));
    else if (opt == 5)
      tree.ins(x), printf("%d\n", tree.val[tree.pre()]), tree.del(x);
    else
      tree.ins(x), printf("%d\n", tree.val[tree.nxt()]), tree.del(x);
  }
  return 0;
}