代码如下：
## Splay
```cpp
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 300000 + 10;
const int kMaxLog = 20;
const int kInf = 2000000000;
struct SplayTree {
struct Node {
int son[2], fa;
int val;
int cnt;
int siz;
};
Node tree[kMaxN * kMaxLog];
int top;
inline int NewNode(int val) {
tree[++top] = (Node) {0, 0, 0, val, 1, 1};
return top;
}
inline int NewTree(int val) {
int root = NewNode(val);
Insert(root, -kInf);
Insert(root, kInf);
return root;
}
inline bool GetPos(int x) { return tree[tree[x].fa].son[1] == x; }
inline bool GetDir(int x, int val) { return tree[x].val < val; }
inline void PushUp(int x) {
tree[x].siz = tree[tree[x].son[0]].siz +
tree[tree[x].son[1]].siz + tree[x].cnt;
}
inline void Connect(int son, int fa, bool pos) {
if (fa) tree[fa].son[pos] = son;
if (son) tree[son].fa = fa;
}
inline void Rotate(int x) {
int y = tree[x].fa;
int z = tree[y].fa;
bool k = GetPos(x);
if (z) tree[z].son[GetPos(y)] = x;
tree[x].fa = z;
Connect(tree[x].son[!k], y, k);
Connect(y, x, !k);
PushUp(y);
}
inline void Splay(int x, int target = 0) {
while (tree[x].fa != target) {
int y = tree[x].fa;
if (tree[y].fa != target) Rotate(GetPos(x) == GetPos(y) ? y : x);
Rotate(x);
}
PushUp(x);
}
inline int Find(int& root, int val) {
int x = root;
while (tree[x].val != val && tree[x].son[GetDir(x, val)])
x = tree[x].son[GetDir(x, val)];
Splay(x);
root = x;
return x;
}
inline void Insert(int& root, int val) {
int x = root, y = 0;
while (x && tree[x].val != val) {
tree[x].siz++;
y = x;
x = tree[x].son[GetDir(x, val)];
}
if (!x) {
x = NewNode(val);
Connect(x, y, GetDir(y, val));
} else {
tree[x].siz++;
tree[x].cnt++;
}
Splay(x);
root = x;
}
inline int GetRank(int& root, int val) { // Bug!!!
// 不能直接这样做！！！若val不存在则会WA
/*int x = Find(val);
return tree[tree[x].son[0]].siz + 1;*/
int x = root;
int ans = 0;
while (1) {
if (tree[x].val <= val) ans += tree[tree[x].son[0]].siz;
if (tree[x].val < val) ans += tree[x].cnt;
if (tree[x].val == val || !tree[x].son[GetDir(x, val)]) {
Splay(x);
root = x;
return ans + 1;
} else {
x = tree[x].son[GetDir(x, val)];
}
}
}
inline int GetKth(int& root, int k) {
k++;
int x = root;
if (tree[x].siz <= k) return -1;
while (1) {
int lson = tree[x].son[0];
if (k <= tree[lson].siz) {
x = lson;
} else if (k <= tree[lson].siz + tree[x].cnt) {
Splay(x);
root = x;
return tree[x].val;
} else {
k -= tree[lson].siz + tree[x].cnt;
x = tree[x].son[1];
}
}
}
void Merge(int& root, int x) {
if (!x) return;
Merge(root, tree[x].son[0]);
if (tree[x].val != kInf && tree[x].val != -kInf)
Insert(root, tree[x].val);
Merge(root, tree[x].son[1]);
}
void Print(int x) {
if (!x) return;
Print(tree[x].son[0]);
printf("%d ", tree[x].val);
Print(tree[x].son[1]);
}
void PrintTree(const char* message, int root) {
printf("%s[ ", message);
Print(root);
printf("]\n");
}
};
struct UnionSet {
int father[kMaxN];
UnionSet() {
for (int i = 0; i < kMaxN; i++) father[i] = i;
}
int Find(int x) {
if (father[x] == x) {
return x;
} else {
return father[x] = Find(father[x]);
}
}
bool Union(int x, int y) {
int i = Find(x);
int j = Find(y);
father[j] = i;
return i != j;
}
};
SplayTree T;
UnionSet S;
int n, m, q;
int root[kMaxN];
int island[kMaxN];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
root[i] = T.NewTree(a);
island[a] = i;
}
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
u = S.Find(u);
v = S.Find(v);
if (u != v) {
// T.PrintTree("Splay u = ", root[u]);
// T.PrintTree("Splay v = ", root[v]);
if (T.tree[root[u]].siz < T.tree[root[v]].siz) {
swap(root[u], root[v]);
}
T.Merge(root[u], root[v]);
// T.PrintTree("Splay u + v = ", root[u]);
S.father[v] = u;
}
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
char opt;
int x, y;
scanf("%s %d %d", &opt, &x, &y);
if (opt == 'Q') {
int ans = T.GetKth(root[S.Find(x)], y);
if (ans == -1) {
printf("-1\n");
} else {
printf("%d\n", island[ans]);
}
} else {
assert(opt == 'B');
x = S.Find(x);
y = S.Find(y);
if (x != y) {
// T.PrintTree("Splay x = ", root[x]);
// T.PrintTree("Splay y = ", root[y]);
if (T.tree[root[x]].siz < T.tree[root[y]].siz) {
swap(root[x], root[y]);
}
T.Merge(root[x], root[y]);
// T.PrintTree("Splay x + y = ", root[x]);
S.father[y] = x;
}
}
}
return 0;
}
```
## Treap
```cpp
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 300000 + 10;
const int kMaxLog = 20;
const int kInf = 2000000000;
struct FhqTreap {
struct Node {
int val;
int l,r;
int siz;
int pri;
};
Node tree[kMaxN * kMaxLog];
int top;
inline int NewNode(int val) {
top++;
tree[top].val = val;
tree[top].l = tree[top].r = 0;
tree[top].siz = 1;
tree[top].pri = rand();
return top;
}
inline void PushUp(int x) {
tree[x].siz = tree[tree[x].l].siz + tree[tree[x].r].siz + 1;
}
int Merge(int x, int y) {
if (!x || !y) {
return x | y;
} else if (tree[x].pri < tree[y].pri) {
tree[x].r = Merge(tree[x].r, y);
PushUp(x);
return x;
} else {
tree[y].l = Merge(x, tree[y].l);
PushUp(y);
return y;
}
}
void SplitByVal(int node, int& x, int& y, int k) {
if (!node) {
x = y = 0;
} else if (tree[node].val <= k) {
x = node;
SplitByVal(tree[x].r, tree[x].r, y, k);
PushUp(x);
} else {
y = node;
SplitByVal(tree[y].l, x, tree[y].l, k);
PushUp(y);
}
}
void SplitBySiz(int node, int& x, int& y, int k) {
if (!node) {
x = y = 0;
} else if (tree[tree[node].l].siz + 1 <= k) {
x = node;
SplitBySiz(tree[x].r, tree[x].r, y, k - tree[tree[x].l].siz - 1);
PushUp(x);
} else {
y = node;
SplitBySiz(tree[y].l, x, tree[y].l, k);
PushUp(y);
}
}
inline void Insert(int& root, int val) {
int x, y;
SplitByVal(root, x, y, val);
root = Merge(Merge(x, NewNode(val)), y);
}
inline int GetKth(int& root, int k) {
if (k > tree[root].siz) return -1;
int x, y;
SplitBySiz(root, x, y, k);
int node = x;
while (tree[node].r) node = tree[node].r;
root = Merge(x, y);
return tree[node].val;
}
void MergeTree(int& root, int x) {
if (!x) return;
MergeTree(root, tree[x].l);
Insert(root, tree[x].val);
MergeTree(root, tree[x].r);
}
};
struct UnionSet {
int father[kMaxN];
UnionSet() {
for (int i = 0; i < kMaxN; i++) father[i] = i;
}
int Find(int x) {
if (father[x] == x) {
return x;
} else {
return father[x] = Find(father[x]);
}
}
bool Union(int x, int y) {
int i = Find(x);
int j = Find(y);
father[j] = i;
return i != j;
}
};
FhqTreap T;
UnionSet S;
int n, m, q;
int root[kMaxN];
int island[kMaxN];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
root[i] = T.NewNode(a);
island[a] = i;
}
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
u = S.Find(u);
v = S.Find(v);
if (u != v) {
// T.PrintTree("Splay u = ", root[u]);
// T.PrintTree("Splay v = ", root[v]);
if (T.tree[root[u]].siz < T.tree[root[v]].siz) {
swap(root[u], root[v]);
}
T.MergeTree(root[u], root[v]);
// T.PrintTree("Splay u + v = ", root[u]);
S.father[v] = u;
}
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
char opt;
int x, y;
scanf("%s %d %d", &opt, &x, &y);
if (opt == 'Q') {
int ans = T.GetKth(root[S.Find(x)], y);
if (ans == -1) {
printf("-1\n");
} else {
printf("%d\n", island[ans]);
}
} else {
assert(opt == 'B');
x = S.Find(x);
y = S.Find(y);
if (x != y) {
// T.PrintTree("Splay x = ", root[x]);
// T.PrintTree("Splay y = ", root[y]);
if (T.tree[root[x]].siz < T.tree[root[y]].siz) {
swap(root[x], root[y]);
}
T.MergeTree(root[x], root[y]);
// T.PrintTree("Splay x + y = ", root[x]);
S.father[y] = x;
}
}
}
return 0;
}
```
by longlongzhu123 @ 2019-04-24 08:56:28
望大佬帮忙解答一下，谢谢！
by longlongzhu123 @ 2019-04-24 08:57:26
手动@[command_block](/space/show?uid=58705) @[lahlah](/space/show?uid=31656) （滑稽）
帮忙看一下？谢谢！
by longlongzhu123 @ 2019-04-24 09:05:38
哪来的这么多操作,我就四个函数
```cpp
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int Ins(int &k,int l,int r,int val){
if(!k)k=++sz;
if(l==r)return nd[k].sum=1;
if((val<=mid&&Ins(nd[k].ls,l,mid,val))||Ins(nd[k].rs,mid+1,r,val));
return nd[k].sum=nd[nd[k].ls].sum+nd[nd[k].rs].sum,1;
}
int Ask(int k,int l,int r,int rk){
if(l==r)return l;
return nd[nd[k].ls].sum>=rk?Ask(nd[k].ls,l,mid,rk):Ask(nd[k].rs,mid+1,r,rk-nd[nd[k].ls].sum);
}
int Mrg(int a,int b){
if(!a||!b)return a|b;
nd[a].ls=Mrg(nd[a].ls,nd[b].ls),nd[a].rs=Mrg(nd[a].rs,nd[b].rs);
nd[a].sum=nd[nd[a].ls].sum+nd[nd[a].rs].sum;
return a;
}
```
by The_KOG @ 2019-04-24 09:10:40
@[The_KOG](/space/show?uid=98051) 你真的看过讨论标题吗？
by かなで @ 2019-04-24 09:14:53
splay启发式合并的常数好像确实可以抵消掉log的差距
by 142857cs @ 2019-04-24 09:20:48
好像那个常数在OI范围内完全就废了
by 142857cs @ 2019-04-24 09:21:39
@[142857cs](/space/show?uid=35760) emmm? QAQ
by longlongzhu123 @ 2019-04-24 09:23:23
我看了一下原论文，看不懂，但是结论中出现了上万的常数和超过1e9的低次项。。。
by 142857cs @ 2019-04-24 09:24:03
所以说这个结论在OI范围内可能没有意义
by 142857cs @ 2019-04-24 09:25:09