伸展树
<pre><code class="language-cpp">#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
namespace Splay_Tree{
//维护序列的伸展树，
//如果维护序列（位置）的话，可以用merge函数来合并平衡树（大小关系已知，大小关系就是位置关系）
//如果维护的是值本身，就要用 dsu_merge进行启发式合并（任何时候不要用merge）
struct Node {
int v = 0;//该节点值
int fa = 0;
int ch[2] = {0, 0};
int siz = 0;//子树大小
int max = 0;//子树最大值
int rev = 0;//翻转标记
};
Node tree[maxn];
bool findd(int x){
return tree[tree[x].fa].ch[0] != x;
}
void connect(int x, int fa, int son){ // 把x放到fa的左子树，保证fa的左子树为空，否则要把最值spaly到根。
if (x) {
tree[x].fa = fa;
}
if (fa) {
tree[fa].ch[son] = x;
}
}
void rev(int &x) {//序列反正，一般来说不维护序列用不到这个
tree[x].rev ^= 1;
swap(tree[x].ch[0], tree[x].ch[1]);
}
void pushdown(int x){//下传翻转标记
if (tree[x].rev) {
int ls = tree[x].ch[0], rs = tree[x].ch[1];
rev(ls);
rev(rs);
tree[x].rev = 0;
}
}
void pushup(int x){
if (x) {
tree[x].siz = tree[tree[x].ch[0]].siz + tree[tree[x].ch[1]].siz + 1;
tree[x].max = std::max(tree[x].v, std::max(tree[tree[x].ch[0]].max, tree[tree[x].ch[1]].max));
}
}
void rotate(int x)
{
int y = tree[x].fa;
int r = tree[y].fa;
int yson = findd(x);
int rson = findd(y);
int b = tree[x].ch[!yson];
connect(b, y, yson);
connect(y, x, !yson);
connect(x, r, rson);
pushup(y);
pushup(x);
}
void splay(int x, int to){//把x上旋到to位置
to = tree[to].fa;
while (tree[x].fa != to) {
int y = tree[x].fa;
if (tree[y].fa == to) {
rotate(x);
} else if (findd(x) == findd(y)) {
rotate(y);
rotate(x);
} else {
rotate(x);
rotate(x);
}
}
}
int arank(int x, int root){//以root为根的树，拍第x名的是谁，第x名充当新根并返回
int now = root;
while (true) {
pushdown(now);
int used = tree[now].siz - tree[tree[now].ch[1]].siz;
if (x == used) {
splay(now, root);
return now;
}
if (x < used) {
now = tree[now].ch[0];
} else {
x -= used;
now = tree[now].ch[1];
}
}
}
int merge(int x, int y){//把x树与y树合并，保证x都比y小或者大。
if (!x) {
return y;
}
if (!y) {
return x;
}
pushdown(x);
pushdown(y);
y = arank(1, y);
connect(x, y, 0);
pushup(y);
return y;
}
int insert(int x, int y){//把y
int now = x;
while(now){
pushdown(now);
int son = tree[y].v > tree[now].v;//注意，我这里是左子树小于右子树
if(!tree[now].ch[son]){
connect(y, now, son);
pushup(now);
splay(y, x);
return y;
}
now = tree[now].ch[son];
}
return y;
}
int dsu_on_merge(int x, int y){
pushdown(y);
if(tree[y].ch[0]) x = dsu_on_merge(x, tree[y].ch[0]);
if(tree[y].ch[1]) x = dsu_on_merge(x, tree[y].ch[1]);
tree[y].siz = 1;
tree[y].ch[0] = tree[y].ch[1] = 0;
tree[y].max = tree[y].v;
return insert(x, y);
}
int dsu_merge(int x, int y){//把平衡树y与x启发式合并 ，返回新根
if(tree[x].siz < tree[y].siz) swap(x, y);
return dsu_on_merge(x, y);
}
void split(int t, int k, int& x, int& y){//把以t为根的树分成左边k个，右边n-k个，左树根为x，右树根为y
if(!k){
x = 0;
y = t;
return;
}
pushdown(t);
x = arank(k, t);
y = tree[x].ch[1];
tree[y].fa = 0;
tree[x].ch[1] = 0;
pushup(x);
}
int getlen(int p, int x){//以p为根的树，x在其中拍第几名，没有的话返回0
pushdown(p);
if (!p) {
return 0;
} else if (tree[tree[p].ch[0]].max > x) {
return getlen(tree[p].ch[0], x);
} else if (tree[p].v > x) {
return tree[tree[p].ch[0]].siz;
} else {
return getlen(tree[p].ch[1], x) + tree[tree[p].ch[0]].siz + 1;
}
}
}
</code></pre>