这道题啊。。。
一开始学习的时候遇到了一篇讲的超级好的博客：rentenglong 的博客
这篇大家一定要去瞅瞅，讲的炒鸡详细（就是代码有点锅。。。）
后来找到一份和TA码风差不多的，才完善了一哈qwq
不过最终还是过了
Code:
#include <bits/stdc++.h> #define root e[0].son[1] using namespace std; int read() { int re = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = -f; ch = getchar();} while ('0' <= ch && ch <= '9') {re = re * 10 + ch - '0'; ch = getchar();} return re * f; } const int N = 1e5 + 3; const int INF = 1e7 + 3; int n, cnt; struct node{ int v, father;//储存键值，父亲节点 int son[2];//存储左右孩子，son[0]为左，son[1]为右 int sum;//存储这个节点子树共有多少 元素 (元素包括sum + recy) int recy;//存储相同键值重复多少次 }e[N]; void update(int x) {//合并 e[x].sum = e[e[x].son[0]].sum + e[e[x].son[1]].sum + e[x].recy; } int identify(int x) {//确定当前节点与父亲节点的关系 return e[e[x].father].son[0] == x ? 0 : 1; } void connect(int x, int fa, int son) {//连接两个节点 e[x].father = fa; e[fa].son[son] = x; } void rotate(int x) {//核心函数之一，旋转 int y = e[x].father; int mroot = e[y].father; int mrootson = identify(y); int yson = identify(x); int B = e[x].son[yson ^ 1]; connect(B, y, yson); connect(y, x, (yson ^ 1)); connect(x, mroot, mrootson); update(y);//y在上，先更新y update(x); } void splay(int at, int to) {//核心函数 to = e[to].father; while (e[at].father != to) { int up = e[at].father; if (e[up].father == to) { rotate(at); } else if (identify(at) == identify(up)) {//当自己的父亲与爷爷在一条直线上时，先旋转父亲 rotate(up); rotate(at); } else {//不在同一直线上就旋转两次 rotate(at); rotate(at); } } } int newpoint(int v, int fa) {//添加新节点 e[++cnt].father = fa; e[cnt].v = v; e[cnt].sum = e[cnt].recy = 1; return cnt; } void Insert(int x) { int now = root; if(!root){//特判没根的情况 newpoint(x, 0); root = cnt; } else { while (true) { e[now].sum++;//经过的点子树中元素都要++ if (e[now].v == x) { e[now].recy++;//重复 splay(now, root); return; } int next = x < e[now].v ? 0 : 1;//判断该走左孩子还是右孩子 if (!e[now].son[next]) { int add = newpoint(x, now); e[now].son[next] = add; splay(add, root); return; } now = e[now].son[next]; } } } int find(int v) {//查询键值为v的点的位置 int now = root; while (true) { if (e[now].v == v) { splay(now, root);//划重点，下面有用 return now; } int next = v < e[now].v ? 0 : 1; if (!e[now].son[next]) { return 0; } now = e[now].son[next]; } } void delet(int x) {//删除节点 int now = find(x);//注意find()函数中已经将x转为根节点 if (!now) { return; } if (e[now].recy > 1) {//如果有重复，直接减去即可 e[now].recy--; e[now].sum--; } else { if (!e[now].son[0] && !e[now].son[1]) {//如果没有左右孩子，说明就一个点 root = 0; } else if (!e[now].son[0]) {//如果没有左孩子，直接将右孩子提为根节点 root = e[now].son[1]; e[root].father = 0; } else {//左右孩子都有，先将左子树中最大的节点转到左孩子的位置，然后提为根节点，把右孩子连到该节点之下 int lef = e[now].son[0]; while (e[lef].son[1]) {//找左子树中最大的节点 lef = e[lef].son[1]; } splay(lef, e[now].son[0]); connect(e[now].son[1], lef, 1); connect(lef, 0, 1); update(lef); } } } int _rank(int v) { int now = find(v);//因为find()已经将v转为根节点，所以直接求即可 return e[e[now].son[0]].sum + 1; } int arank(int x) { int now = root; while (true) { int used = e[now].sum - e[e[now].son[1]].sum; //如果x大于左子树元素，并且小于等于当前点的左子树的sum加上本节点的recy的值，那么当前的点就是要找的点 //因为此时说明该x是当前节点重复值中的一个 if (e[e[now].son[0]].sum < x && x <= used) { splay(now, root); return e[now].v; } if (x < used) {//小于则向左子树寻找 now = e[now].son[0]; } else {//大于则减去该值，再向右子树寻找 x -= used; now = e[now].son[1]; } } } int lower(int v) {//前驱 int now = root; int ans = -INF; while (now) { if (e[now].v < v && e[now].v > ans) { ans = e[now].v; } if (v > e[now].v) { now = e[now].son[1]; } else { now = e[now].son[0]; } } return ans; } int upper(int v) {//后继 int now = root; int ans = INF; while(now) { if (e[now].v > v && e[now].v < ans) { ans = e[now].v; } if (v < e[now].v) { now = e[now].son[0]; } else { now = e[now].son[1]; } } return ans; } int main () { n = read(); while (n--) { int o = read(); int x = read(); if (o == 1) { Insert(x); } else if (o == 2) { delet(x); } else if (o == 3) { printf("%d\n", _rank(x)); } else if (o == 4) { printf("%d\n", arank(x)); } else if (o == 5) { printf("%d\n", lower(x)); } else if (o == 6) { printf("%d\n", upper(x)); } } return 0; }