题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3224
平衡树入门题，学习学习。
splay(学习yyb巨佬)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
const int INF = 1e9;
inline void read(int &n) {
register int x = , t = ;
register char ch = getchar();
while (ch != '-' && (ch<'' || ch>''))ch = getchar();
if (ch == '-') { t = -; ch = getchar(); }
while (ch >= ''&&ch <= '') { x = x * + ch - ; ch = getchar(); }
n = x * t;
}
int root, len;
struct node {
int fa;//节点的父节点
int siz;//节点的子树数量
int ch[];//节点的左(0)子节点和右(1)子节点
int val;//节点的值
int num;//节点的值的数量
}a[maxn];
inline void pushup(int x) {//更新当前节点的子树//当前子树的大小是左子树大小加上右子树大小当前当前节点个数
a[x].siz = a[a[x].ch[]].siz + a[a[x].ch[]].siz + a[x].num;
}
inline void rotate(int x) {//旋转操作//将x旋转到x的父亲的位置
int y = a[x].fa;//y是x的父节点
int z = a[y].fa;//z是x的祖父节点
int k = (a[y].ch[] == x);//求x是y的左(0)还是右(1)节点
a[z].ch[a[z].ch[] == y] = x;//求y是z的左(0)还是右(1)节点，同时将x放在该位置
a[x].fa = z;//修改x的父节点
a[y].ch[k] = a[x].ch[k ^ ];//把x的儿子给y
a[a[x].ch[k ^ ]].fa = y;//更新父节点为y
a[x].ch[k ^ ] = y;//y变为x的子节点
a[y].fa = x;//y的父亲更新为x
pushup(y), pushup(x);//更新y和x的子节点数量
}
inline void splay(int x, int goal) {//将x旋转为goal的子节点
while (a[x].fa != goal) {
int y = a[x].fa;
int z = a[y].fa;
if (z != goal)
(a[y].ch[] == x) ^ (a[z].ch[] == y) ? rotate(x) : rotate(y);
//如果x和y同为左儿子或者右儿子先旋转y
//如果x和y不同为左儿子或者右儿子先旋转x
//如果不双旋的话，旋转完成之后树的结构不会变化
rotate(x);
}
if (goal == )
root = x;
}
inline void insert(int x) {
int now = root, fa = ;//当前节点now和now的父节点fa
while (now&&a[now].val != x) {//当now存在并且没有移动到当前的值
fa = now;//父节点变为now
now = a[now].ch[x > a[now].val];//x大于当前位置则now向右，否则now向左
}
if (now)//这个值出现过
a[now].num++;//值增加
else {//这个值第一次出现，要新建一个节点来存放
now = ++len;
if (fa)//父节点不是根节点(0)
a[fa].ch[x > a[fa].val] = now;
//初始化节点
a[now].ch[] = a[now].ch[] = ;
a[now].siz = ;
a[now].num = ;
a[now].fa = fa;
a[now].val = x;
}
splay(now, );
}
inline void Find(int x) {//查找x的位置，并将其旋转到根节点
int now = root;
if (!now)return;//数为空
while (a[now].ch[x > a[now].val] && x != a[now].val)////当存在儿子并且当前位置的值不等于x
now = a[now].ch[x > a[now].val];
splay(now, );//把当前位置旋转到根节点
}
inline int Next(int x, int flag) {//查找x的前驱(0)或者后继(1)
Find(x);
int now = root;
if (a[now].val > x&&flag)return now;//如果当前节点的值大于x并且要查找的是后继
if (a[now].val < x && !flag)return now;//如果当前节点的值小于x并且要查找的是前驱
now = a[now].ch[flag];//查找后继的话在右儿子上找，前驱在左儿子上找
while (a[now].ch[flag ^ ])now = a[now].ch[flag ^ ];
return now;
}
inline void Delete(int x) {//删除一个x
int last = Next(x, );//查找x的前驱
int next = Next(x, );//查找x的后继
splay(last, ), splay(next, last);
//将前驱旋转到根节点，后继旋转到根节点下面
//很明显，此时后继是前驱的右儿子，x是后继的左儿子，并且x是叶子节点
int now = a[next].ch[];//后继的左儿子，也就是x
if (a[now].num > ) {//超过一个就删除一个
a[now].num--;
splay(now, );
}
else
a[next].ch[] = ;//直接删除 }
inline int kth(int k) {//查找第k小的数
int now = root;
if (a[now].siz < k)
return ;
while () {
int y = a[now].ch[];//y是左儿子
if (k > a[y].siz + a[now].num) {//如果排名比左儿子的大小和当前节点的数量要大
k -= a[y].siz + a[now].num;//排名减小
now = a[now].ch[];//定在右儿子上找
}
else {
if (k <= a[y].siz)
now = y;
else
return a[now].val;
}
}
}
int main() {
int n;
read(n);
root = , len = ;
insert();
insert(-);
while (n--) {
int q, x;
read(q), read(x);
if (q == )
insert(x);
else if (q == )
Delete(x);
else if (q == ) {
Find(x);
printf("%d\n", a[a[root].ch[]].siz);
}
else if (q == )
printf("%d\n", kth(x + ));
else if (q == )
printf("%d\n", a[Next(x, )].val);
else if (q == )
printf("%d\n", a[Next(x, )].val);
}
}
无旋Treap(学习fzszkl巨佬)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
int Siz[maxn], ls[maxn], rs[maxn], val[maxn], pos[maxn], root;
int cnt;
int send = ;
inline int Rand() {
send ^= send << ;
send ^= send >> ;
send ^= send << ;
return send;
}
inline int New(int x) {
cnt++;
pos[cnt] = Rand();
Siz[cnt] = ;
val[cnt] = x;
return cnt;
}
inline void up(int x) {
Siz[x] = Siz[ls[x]] + Siz[rs[x]] + ;
}
void split_size(int x, int siz, int &A, int &B) {
if (x == )return (void)(A = B = );
if (siz <= Siz[ls[x]])
B = x, split_size(ls[x], siz, A, ls[x]);
else
A = x, split_size(rs[x], siz - Siz[ls[x]] - , rs[x], B);
up(x);
}
void split_val(int x, int v, int &A, int &B) {
if (x == )return (void)(A = B = );
if (v < val[x])
B = x, split_val(ls[x], v, A, ls[x]);
else
A = x, split_val(rs[x], v, rs[x], B);
up(x);
}
int Merge(int A, int B) {
if (A == || B == )return A | B;
int ans;
if (pos[A] > pos[B])ans = A, rs[A] = Merge(rs[A], B);
else ans = B, ls[B] = Merge(A, ls[B]);
up(ans);
return ans;
}
void dfs(int x) {
if (x == )
return;
printf("%d ", x);
dfs(ls[x]);
dfs(rs[x]);
}
void insert(int x) {
int A, B;
split_val(root, x - , A, B);
root = Merge(Merge(A, New(x)), B);
}
void Delete(int x) {
int A, B, C, D;
split_val(root, x - , A, B);
split_size(B, , C, D);//C就是删除的节点
root = Merge(A, D);
}
int Rank(int x) {//查x的排名
int A, B, ans;
split_val(root, x - , A, B);
ans = Siz[A] + ;
root = Merge(A, B);
return ans;
}
int getR(int x) {//查第x名是什么
int A, B, C, D, ans;
split_size(root, x - , A, B);
split_size(B, , C, D);
ans = val[C];
Merge(Merge(A, C), D);
return ans;
}
int last(int x) {
int A, B, C, D, ans;
split_val(root, x - , A, B);
split_size(A, Siz[A] - , C, D);
ans = val[D];
Merge(Merge(C, D), B);
return ans;
}
int Next(int x) {
int A, B, C, D, Ans;
split_val(root, x, A, B);
split_size(B, , C, D);
Ans = val[C];
root = Merge(Merge(A, C), D);
return Ans;
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
int opt, x;
scanf("%d%d", &opt, &x);
if (opt == )
insert(x);
else if (opt == )
Delete(x);
else if (opt == )
printf("%d\n", Rank(x));
else if (opt == )
printf("%d\n", getR(x));
else if (opt == )
printf("%d\n", last(x));
else if (opt == )
printf("%d\n", Next(x));
}
return ;
}