记录编号	601280	评测结果	AAAAAAAAAA
题目名称	1829.[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.466 s
提交时间	2025-06-09 22:11:57	内存使用	1.89 MiB

#include <cstdio>
#include <cstdlib>
#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')

template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T> void write(T x, char ed = '\n') {
  if (x < 0) putchar('-'), x = -x;
  static int sta[64], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while(x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}

const int MAXN = 1e5 + 10;

struct NODE {
  int ls, rs;
  int siz;
  int val;
  int qwq;
} node[MAXN];

int nodeNum;

int New(int val) {
  nodeNum++;
  node[nodeNum].qwq = rand();
  node[nodeNum].siz= 1;
  node[nodeNum].val = val;
  return nodeNum;
}

void PushUp(int root) {
  node[root].siz = node[node[root].ls].siz + node[node[root].rs].siz + 1;
}

void SplitSize(int root, int siz, int &A, int &B) {
  if (root == 0) return (void)(A = B = 0);
  if (node[node[root].ls].siz >= siz) {
    B = root;
    SplitSize(node[root].ls, siz, A, node[root].ls);
  } else {
    A = root;
    SplitSize(node[root].rs, siz - node[node[root].ls].siz - 1, node[root].rs, B);
  }
  PushUp(root);
}

void SplitValue(int root, int val, int &A, int &B) {
  if (root == 0) return (void)(A = B = 0);
  if (node[root].val > val) {
    B = root;
    SplitValue(node[root].ls, val, A, node[root].ls);
  } else {
    A = root;
    SplitValue(node[root].rs, val, node[root].rs, B);
  }
  PushUp(root);
}

int Merge(int A, int B) {
  if (A == 0 || B == 0) return A | B;
  int res;
  if (node[A].qwq > node[B].qwq) {
    res = A;
    node[A].rs = Merge(node[A].rs, B);
  } else {
    res = B;
    node[B].ls = Merge(A, node[B].ls);
  }
  PushUp(res);
  return res;
}

int root;
void Insert(int val) {
  int A, B;
  SplitValue(root, val - 1, A, B);
  root = Merge(Merge(A, New(val)), B);
}

void Delete(int val) {
  int A, B, C, D;
  SplitValue(root, val - 1, A, B);
  SplitSize(B, 1, C, D);
  root = Merge(A, D);
}

int GetRank(int val) {
  int A, B, ans;
  SplitValue(root, val - 1, A, B);
  ans = node[A].siz + 1;
  root = Merge(A, B);
  return ans;
}

int GetK(int rank) {
  int A, B, C, D, ans;
  SplitSize(root, rank - 1, A, B);
  SplitSize(B, 1, C, D);
  ans = node[C].val;
  root = Merge(Merge(A, C), D);
  return ans;
}

int GetNxt(int val) {
  int A, B, C, D, ans;
  SplitValue(root, val, A, B);
  SplitSize(B, 1, C, D);
  ans = node[C].val;
  root = Merge(Merge(A, C), D);
  return ans;
}

int GetPre(int val) {
  int A, B, C, D, ans;
  SplitValue(root, val - 1, A, B);
  SplitSize(A, node[A].siz - 1, C, D);
  ans = node[D].val;
  root = Merge(Merge(C, D), B);
  return ans;
}

int q;

int main() {
  freopen("phs.in", "r", stdin);
  freopen("phs.out", "w", stdout);
  q = read<int>();
  while (q--) {
    int op = read<int>(), x = read<int>();
    if (op == 1) Insert(x);
    else if (op == 2) Delete(x);
    else if (op == 3) write(GetRank(x));
    else if (op == 4) write(GetK(x));
    else if (op == 5) write(GetPre(x));
    else if (op == 6) write(GetNxt(x));
  }
  return 0;
}