@dxbdly 2021-07-11T15:18:27.000000Z 字数 16972 阅读 333

FHQ-Treap

OI-算法

图片引自博客（怪我美术太差画不出，找到几个操作是有图的，勉强看看吧）

本文作者 $\operatorname{dxbdly}$ ，转载或引用请加上原文链接

$Update\,\,\,2021.6.8:$ 修润了部分 $Latex$ ，更新了部分代码（虽然注释没了，但应该不打紧），加入了新的例题

$1.$ 前言

我们在学习 $BST$ 时，会发现其实 $BST$ 的复杂度并不稳定

如果我们构造一个单调序列，那么树的形状会变成一条链，单次操作时间复杂度 $O(n)$

那么这时候我们需要一些方法使得 $BST$ 树 $“$ 平衡 $”$

众所周知，平衡树大多带旋转操作，并且码量巨大无比(反正我没写出来过)

今天介绍一种不需要旋转，且 非常好写，非常好写，非常好写 的平衡树 —— $FHQ-Treap$

$2.$ $Treap$ 的思想

说 $FHQ-Treap$ 之前，我们先来看看 $Treap$

$Treap=BST+Heap$ ，即 $BST$ + 堆

他的思想是：对于 $BST$ 树上的每个节点，我们都随机给他一个权值 $rad$ ，我们需要保证 $rad$ 满足堆的性质(大根，小根均可)

则他的期望形状是平衡的。(是不是很玄学，至于怎么证吗……请读者自证）

$3.$ $FHQ-Treap$ 的思想与操作

$Treap$ 维护的操作是通过不断旋转，码量巨大而且常数**

但 $FHQ-Treap$ 用的则是合并 $Merge$ 与分裂 $Split$ 的操作。

对于一个节点，我们需要记录以下变量:

//The code is from dxbdly
struct node {
    int lc, rc;
    int siz, rad, val;
}Tree[maxn << 1];

我们直接来看操作：

$1^o$ $Add$ 操作

动态开点，随机获取 $rad$ 值。

//The code is from dxbdly
inline int Add(int val) { 
    tot++;
    Tree[tot].siz = 1, Tree[tot].lc = Tree[tot].rc = 0, Tree[tot].val = val, Tree[tot].rad = rand();
    return tot;
}

$2^o$ $Update$ 操作

对于一节点由于其左儿子，右儿子有变化，需要重新统计 $siz$

//The code is from dxbdly
inline void Update(int k) { 
    Tree[k].siz = Tree[Tree[k].lc].siz + Tree[Tree[k].rc].siz + 1; 
}

$3^o$ $Merge$ 操作

$Merge$ 操作主要维护堆的性质，将两个 $Treap$ 合成一个，具体可以参考左偏树的合并。

//The code is from dxbdly
inline void Merge(int &k, int a, int b) {
    if(!a || !b) { k = a + b; return ; }
    if(Tree[a].rad <= Tree[b].rad) k = a, Merge(Tree[k].rc, Tree[k].rc, b);
    else k = b, Merge(Tree[k].lc, a, Tree[k].lc);
    Update(k);
}

$4^o$ $Split$ 操作

$Split$ 操作主要满足 $BST$ 性质,有两种写法：

$(1)$ 按权值分裂：

则若分裂标准为 $val$ ,我们要使得分裂出的左树点权值均 $\leq val$ ，右树均 $>val$

分三种情况讨论：

设当前子树根节点为 $i$ ，要分裂出的两棵子树分别为 $a, b$ ，分裂标准为 $val$

$1.$ 若 $i=0:$ $a=b=0$

$2.$ 若 $tree[i].val \leq val：$
由 $BST$ 性质可知，左子树所有点均 $<val$
$a$ 左子树确定我们只需要在右子树递归求 $a$ 的右子树, $b$ 即可

$3.$ 若 $tree[i].val>val:$
同理
我们只需要在左子树递归处理 $a，b$ 的左子树。

代码：

//The code is from dxbdly
inline void Split(int k, int &a, int &b, int val) {
    if(!k) { a = b = 0; return ; }
    if(Tree[k].val <= val) a = k, Split(Tree[k].rc, Tree[k].rc, b, val);
    else b = k, Split(Tree[k].lc, a, Tree[k].lc, val);
    Update(k);
}

$(2)$ 根据 $siz$ 分裂:

标准量为： $val$ ，则左树 $siz$ 均 $\leq val$ ，右树均 $>val$

差不多的讨论方式，可以自己试着推一下。

代码：

//The code is from dxbdly
inline void Split(int k, int &a, int &b, int x) {
    if(!k) { a = b = 0; return ; }
    if(Tree[Tree[k].lc].siz + 1 <= x) a = k, Split(Tree[k].rc, Tree[k].rc, b, x - Tree[Tree[k].lc].siz - 1);
    else b = k, Split(Tree[k].lc, a, Tree[k].lc, x);
    Update(k);
}

$5^o$ $Insert$ 操作

若插入的值为 $val$

则以 $val$ 为标准量 $Split$ 整棵树，

然后 $Add(val)$

最后重新全部 $Merge$ 。

代码：

//The code is from dxbdly
inline void Insert(int &k, int val) {
    int a, b, c = Add(val);
    Split(k, a, b, val), Merge(a, a, c), Merge(k, a, b);
}

$6^o$ $Delte$ 操作

若删除的点权值为 $val$

以 $val$ 为标准量将整棵树 $Split$ 为 $a , b$

再以 $val-1$ 为标准量将 $a$ $Split$ 为 $a, c$ ，这样就可以分离出权值为 $val$ 的点，它为 $c$ 的根节点

将 $c$ 的左右儿子 $Merge$ ，就可以将其删除

然后全部重新 $Merge$

代码：

//The code is from dxbdly
inline void Delte(int &k, int val) {
    int a, b, c;
    Split(k, a, b, val), Split(a, a, c, val - 1);
    Merge(c, Tree[c].lc, Tree[c].rc), Merge(a, a, c), Merge(k, a, b);
}

$7^o$ $Find\_Val$ 操作

我们若想知道排名为 $k$ 的数。

与主席树求第 $k$ 小相似。

如果左子树 $size+1=k$ 则就是当前节点。

如果左子树 $size\geq k$ 则 $k$ 不变，递归左子树找

如果左子树 $size<k$ 则 $k$ 变为 $k-tree[tree[i].lc].size-1$ ，递归右子树找。

代码：

//The code is from dxbdly
inline int Find_Val(int k, int x) {
    while(Tree[Tree[k].lc].siz + 1 != x) {
        if(Tree[Tree[k].lc].siz >= x) k = Tree[k].lc;
        else x -= (Tree[Tree[k].lc].siz + 1), k = Tree[k].rc;
    }
    return Tree[k].val;
}

$8^o$ $Find\_rank$ 操作

我们若想知道权值为 $val$ 的数的排名。

只要将按 $val-1$ 为标准量 $Split$ ，此时左树节点均 $<val$ ，所以左树的 $siz$ 就是答案。

代码：

//The code is from dxbdly
inline int Find_Rnk(int &k, int val) {
    int a, b, ans;
    Split(k, a, b, val - 1), ans = Tree[a].siz + 1, Merge(k, a, b);
    return ans;
}

$9^o$ $Find\_pre$ 操作

我们若想知道权值为 $val$ 的前驱。

只要按 $val-1$ 为标准量 $Split$ ，此时左树的最大节点（排名第 $siz$ )便是前驱。

只需在左树中 $Find\_Val$ 左树的第 $siz$ 即是答案。

代码：

//The code is from dxbdly
inline int Find_Pre(int &k, int val) {
    int a, b, ans;
    Split(k, a, b, val - 1), ans = Find_Val(a, Tree[a].siz), Merge(k, a, b);
    return ans;
}

$10^o$ $Find\_Nex$ 操作

我们若想知道权值为 $val$ 的后继。

只要以 $val$ 为标准量 $Split$ ，此时右树的最小节点(排名为 $1$ )

只要在右树中 $Find\_Val$ 右树的第 $1$ 即使答案

代码：

//The code is from dxbdly
inline int Find_Nex(int &k, int val) {
    int a, b, ans;
    Split(k, a, b, val), ans = Find_Val(b, 1), Merge(k, a, b);
    return ans;
}

$11^o$ 常数优化 —— $Rand$

由于我们的 $FHQ\_Treap$ 需要一个随机权值，而随机函数的常数是极大的。

这使得平衡树上点数过多的时候程序会变慢许多，这里我们可以考虑手写一个 $Rand$

实现方式很简单，取一个大质数 $base$ ，让一个初始值为 $1$ 的 $res$ 每次乘上 $base$ ，自然溢出即可。

const int maxn = 1e5 + 5, base = 13331;
int n, tot, root, res = 1;
inline int Rand() {
    res *= base; return res;
}

好了，平衡树的基本操作我们就讲完了。

时间复杂度 $O(mlogn)$

AC总代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e5 + 5, base = 13331;
int n, tot, root, res = 1;
struct node {
    int lc, rc;
    int siz, rad, val;
}Tree[maxn << 1];
inline int Rand() {
    res *= base; return res;
}   
inline int Add(int val) { 
    tot++;
    Tree[tot].siz = 1, Tree[tot].lc = Tree[tot].rc = 0, Tree[tot].val = val, Tree[tot].rad = Rand();
    return tot;
}
inline void Update(int k) { 
    Tree[k].siz = Tree[Tree[k].lc].siz + Tree[Tree[k].rc].siz + 1; 
}
inline void Split(int k, int &a, int &b, int val) {
    if(!k) { a = b = 0; return ; }
    if(Tree[k].val <= val) a = k, Split(Tree[k].rc, Tree[k].rc, b, val);
    else b = k, Split(Tree[k].lc, a, Tree[k].lc, val);
    Update(k);
}
inline void Merge(int &k, int a, int b) {
    if(!a || !b) { k = a + b; return ; }
    if(Tree[a].rad <= Tree[b].rad) k = a, Merge(Tree[k].rc, Tree[k].rc, b);
    else k = b, Merge(Tree[k].lc, a, Tree[k].lc);
    Update(k);
}
inline void Insert(int &k, int val) {
    int a, b, c = Add(val);
    Split(k, a, b, val), Merge(a, a, c), Merge(k, a, b);
}
inline void Delte(int &k, int val) {
    int a, b, c;
    Split(k, a, b, val), Split(a, a, c, val - 1);
    Merge(c, Tree[c].lc, Tree[c].rc), Merge(a, a, c), Merge(k, a, b);
}
inline int Find_Val(int k, int x) {
    while(Tree[Tree[k].lc].siz + 1 != x) {
        if(Tree[Tree[k].lc].siz >= x) k = Tree[k].lc;
        else x -= (Tree[Tree[k].lc].siz + 1), k = Tree[k].rc;
    }
    return Tree[k].val;
}
inline int Find_Rnk(int &k, int val) {
    int a, b, ans;
    Split(k, a, b, val - 1), ans = Tree[a].siz + 1, Merge(k, a, b);
    return ans;
}
inline int Find_Pre(int &k, int val) {
    int a, b, ans;
    Split(k, a, b, val - 1), ans = Find_Val(a, Tree[a].siz), Merge(k, a, b);
    return ans;
}
inline int Find_Nex(int &k, int val) {
    int a, b, ans;
    Split(k, a, b, val), ans = Find_Val(b, 1), Merge(k, a, b);
    return ans;
}
int main() {
    n = read();
    for(register int i = 1; i <= n; ++i) {
        int op = read(), x = read();
        if(op == 1) Insert(root, x);
        if(op == 2) Delte(root, x);
        if(op == 3) printf("%d\n", Find_Rnk(root, x));
        if(op == 4) printf("%d\n", Find_Val(root, x));
        if(op == 5) printf("%d\n", Find_Pre(root, x));
        if(op == 6) printf("%d\n", Find_Nex(root, x));
    }
    return 0;
}

$4.$ $FHQ-Treap$ 的区间翻转

众所周知， $Splay$ 是支持区间翻转的，其实 $FHQ-Treap$ 也行。

题面

题解：

首先我们考虑如何取出 $[l,r]$ 的区间，考虑以 $siz$ 为标准进行 $Split$ 操作

先 $Split$ 出区间 $[1,r]$ 再将区间 $[1,l - 1]$ $Split$ 出去，就得到了区间 $[l, r]$

再考虑如何实现翻转

我们借用线段树 $lazy\_tage$ 的思想，如果当前区间被翻转则打上标记

每次做 $Split$ 与 $Merge$ 操作时将标记下传

每次下传时，将左右儿子的 $tag \operatorname{xor} 1$ ，再将左右儿子交换，最后将自己的 $tag$ 清空。

注意： $Merge$ 操作是将要参与合并的子树下传

//The code is from dxbdly
inline void Push_Down(int k) {
    if(Tree[k].tag) {
        Tree[Tree[k].lc].tag ^= 1, Tree[Tree[k].rc].tag ^= 1;
        Tree[k].tag = 0, swap(Tree[k].lc, Tree[k].rc);
    }
}

最后中序遍历一遍整棵树，将剩余的标记全部下传，输出即可。

时间复杂度 $O(mlogn)$

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e6 + 5, base = 13331;
int n, m, tot, root, last, res = 1;
struct node {
    int lc, rc;
    int siz, rad, val, tag;
}Tree[maxn << 1];
inline int Rand() {
    res *= base; return res;
}   
inline int Add(int val) { 
    tot++;
    Tree[tot].siz = 1, Tree[tot].lc = Tree[tot].rc = 0, Tree[tot].val = val, Tree[tot].rad = Rand();
    return tot;
}
inline void Update(int k) { 
    Tree[k].siz = Tree[Tree[k].lc].siz + Tree[Tree[k].rc].siz + 1; 
}
inline void Push_Down(int k) {
    if(Tree[k].tag) {
        Tree[Tree[k].lc].tag ^= 1, Tree[Tree[k].rc].tag ^= 1;
        Tree[k].tag = 0, swap(Tree[k].lc, Tree[k].rc);
    }
}
inline void Split(int k, int &a, int &b, int x) {
    if(!k) { a = b = 0; return ; }
    Push_Down(k);
    if(Tree[Tree[k].lc].siz + 1 <= x) a = k, Split(Tree[k].rc, Tree[k].rc, b, x - Tree[Tree[k].lc].siz - 1);
    else b = k, Split(Tree[k].lc, a, Tree[k].lc, x);
    Update(k);
}
inline void Merge(int &k, int a, int b) {
    if(!a || !b) { k = a + b; return ; }
    if(Tree[a].rad <= Tree[b].rad) k = a, Push_Down(k), Merge(Tree[k].rc, Tree[k].rc, b);
    else k = b, Push_Down(k), Merge(Tree[k].lc, a, Tree[k].lc);
    Update(k);
}
inline void Insert(int &k, int val) {
    int a, b, c = Add(val);
    Split(k, a, b, val), Merge(a, a, c), Merge(k, a, b);
}
inline void Change(int &k, int l, int r) {
    int a, b, c;
    Split(k, b, c, r), Split(b, a, b, l - 1), Tree[b].tag ^= 1, Merge(b, b, c), Merge(k, a, b);
}
inline void Get_Ans(int k) {
    if(!k) return ;
    Push_Down(k);
    Get_Ans(Tree[k].lc);
    printf("%d ", Tree[k].val);
    Get_Ans(Tree[k].rc);
}
int main() {
    n = read(), m = read();
    for(register int i = 1; i <= n; ++i) Insert(root, i);
    for(register int i = 1; i <= m; ++i) {
        int l = read(), r = read();
        Change(root, l, r);
    }
    Get_Ans(root);
    return 0;
}

$5.$ 例题

$1^o$ HNOI2002 营业额统计

题面

$(1)$ 分析

模板题，以此将营业额插入平衡树，求出前继和后继，取最小即可

细节：

由于有的点没有前继或后继，在最开始的时候插入 $INF$ 与 $-INF$ 防止查询越界

由于营业额可能相等，可能会导致前继和后继都是自己，所以找前继的时候可以找营业额 $+\,1$ 的前继

代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e6 + 5, base = 13331, INF = 1e9 + 7;
int n, tot, root, res = 1;
struct node {
    int lc, rc;
    int siz, rad, val;
}Tree[maxn << 1];
inline int Rand() {
    res *= base; return res;
}   
inline int Add(int val) { 
    tot++;
    Tree[tot].siz = 1, Tree[tot].lc = Tree[tot].rc = 0, Tree[tot].val = val, Tree[tot].rad = Rand();
    return tot;
}
inline void Update(int k) { 
    Tree[k].siz = Tree[Tree[k].lc].siz + Tree[Tree[k].rc].siz + 1; 
}
inline void Split(int k, int &a, int &b, int val) {
    if(!k) { a = b = 0; return ; }
    if(Tree[k].val <= val) a = k, Split(Tree[k].rc, Tree[k].rc, b, val);
    else b = k, Split(Tree[k].lc, a, Tree[k].lc, val);
    Update(k);
}
inline void Merge(int &k, int a, int b) {
    if(!a || !b) { k = a + b; return ; }
    if(Tree[a].rad <= Tree[b].rad) k = a, Merge(Tree[k].rc, Tree[k].rc, b);
    else k = b, Merge(Tree[k].lc, a, Tree[k].lc);
    Update(k);
}
inline void Insert(int &k, int val) {
    int a, b, c = Add(val);
    Split(k, a, b, val), Merge(a, a, c), Merge(k, a, b);
}
inline int Find_Val(int k, int x) {
    while(Tree[Tree[k].lc].siz + 1 != x) {
        if(Tree[Tree[k].lc].siz >= x) k = Tree[k].lc;
        else x -= (Tree[Tree[k].lc].siz + 1), k = Tree[k].rc;
    }
    return Tree[k].val;
}
inline int Find_Pre(int &k, int val) {
    int a, b, ans;
    Split(k, a, b, val - 1), ans = Find_Val(a, Tree[a].siz), Merge(k, a, b);
    return ans;
}
inline int Find_Nex(int &k, int val) {
    int a, b, ans;
    Split(k, a, b, val), ans = Find_Val(b, 1), Merge(k, a, b);
    return ans;
}
int main() {
    n = read();
    Insert(root, -INF), Insert(root, INF);
    int ans = 0;
    for(register int i = 1; i <= n; ++i) {
        int x = read(); 
        int pre = Find_Pre(root, x + 1), nex = Find_Nex(root, x);
        ans += (i != 1 ? min(x - pre, nex - x) : x);
        Insert(root, x);
    }
    printf("%d", ans);
    return 0;
}

$(2)$ 思考与总结

由于 $FHQ-Treap$ 并不是用旋转实现，在使用时更应当防止越界的情况出现

在一些题目的解决中，提前加入一些边界点，会使得后续的处理更加方便。

$2^o$ TJOI2007 书架

题面

$(1)$ 分析

先将初始的 $n$ 本书放进平衡树，权值为编号，考虑新加进来的一本书。

发现如果按 $siz$ 划分，就不需要考虑之前新加入的书对于位置的影响了，直接 $Insert$ 即可

拿个映射记一下编号对应的名字， $Find\_Val$ 即可。

代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e5 + 5, base = 13331;
int n, m, q, tot, root, res = 1;
struct node {
    int lc, rc;
    int siz, rad, val, tag;
}Tree[maxn << 1];
char s[maxn << 1][15];
inline int Rand() {
    res *= base; return res;
}   
inline int Add(int val) { 
    tot++;
    Tree[tot].siz = 1, Tree[tot].lc = Tree[tot].rc = 0, Tree[tot].val = val, Tree[tot].rad = Rand();
    return tot;
}
inline void Update(int k) { 
    Tree[k].siz = Tree[Tree[k].lc].siz + Tree[Tree[k].rc].siz + 1; 
}
inline void Split(int k, int &a, int &b, int x) {
    if(!k) { a = b = 0; return ; }
    if(Tree[Tree[k].lc].siz + 1 <= x) a = k, Split(Tree[k].rc, Tree[k].rc, b, x - Tree[Tree[k].lc].siz - 1);
    else b = k, Split(Tree[k].lc, a, Tree[k].lc, x);
    Update(k);
}
inline void Merge(int &k, int a, int b) {
    if(!a || !b) { k = a + b; return ; }
    if(Tree[a].rad <= Tree[b].rad) k = a, Merge(Tree[k].rc, Tree[k].rc, b);
    else k = b, Merge(Tree[k].lc, a, Tree[k].lc);
    Update(k);
}
inline void Insert(int &k, int val, int x) {
    int a, b, c = Add(val);
    Split(k, a, b, x - 1), Merge(a, a, c), Merge(k, a, b);
}
inline int Find_Val(int k, int x) {
    while(Tree[Tree[k].lc].siz + 1 != x) {
        if(Tree[Tree[k].lc].siz >= x) k = Tree[k].lc;
        else x -= (Tree[Tree[k].lc].siz + 1), k = Tree[k].rc;
    }
    return Tree[k].val;
}
int main() {
    n = read();
    for(register int i = 1; i <= n; ++i) { Insert(root, i, i), scanf("%s", s[i]); }
    m = read();
    for(register int i = 1, x; i <= m; ++i) { scanf("%s", s[n + i]), x = read() + 1, Insert(root, n + i, x); }
    q = read();
    while(q--) {
        int x = read() + 1;
        printf("%s\n", s[Find_Val(root, x)]);
    }
    return 0;
}

$(2)$ 思考与总结

由于 $FHQ-Treap$ 有独特的 $Split$ 操作

所以我们做题时可以考虑以不同参数为划分标准的效果，说不定会有意想不到的收获

$3^o$ HNOI2012 永无乡

题面

$(1)$ 分析

看到询问操作，容易想到使用平衡树来解决

考虑修改操作，如果将一个连通块看成一颗平衡树，我们相当于就是要做平衡树合并

考虑暴力将其中一颗平衡树的每一个点拆下来， $Insert$ 到另外一棵树中去

这样的复杂度最高是 $O(n ^ 2)$ 的，不可取

由于复杂度上限在合并操作上，可以考虑 $dsu$ （启发式合并）

我们考虑合并时，将 $siz$ 小的平衡树合并到 $siz$ 大的树上。

再来分析一下时间复杂度：

由于每次合并都是将小的插入大的，所以 $siz$ 至少会变成小 $siz$ 树的 $2$ 倍

所以最多被合并 $\log n$ 次，时间复杂度 $O(n \log^2 n)$ 可以通过

细节：

合并之后新的根是不确定的，所以要建一个并查集维护每个点所在树的根，方便查询。

拆点下来的时候，要将点的信息重置再 $Insert$

所有操作都需先找到点 $x$ 对应的根，以根来执行

代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e5 + 5, base = 13333;
int n, m, q, res = 1, tot;
int p[maxn];
struct node {
    int lc, rc, fa;
    int val, rad, siz;
}Tree[maxn];
inline int Rand() {
    res *= base; return res;
}
inline int Add(int val) {
    tot++, Tree[tot].lc = Tree[tot].rc = 0;
    Tree[tot].val = val, Tree[tot].rad = Rand(), Tree[tot].siz = 1, Tree[tot].fa = tot;
    return tot;
}
inline void Update(int k) { 
    Tree[k].siz = Tree[Tree[k].lc].siz + Tree[Tree[k].rc].siz + 1; 
}
inline void Split(int k, int &a, int &b, int val) {
    if(!k) { a = 0, b = 0; return ; }
    if(Tree[k].val <= val) a = k, Split(Tree[k].rc, Tree[k].rc, b, val);
    else b = k, Split(Tree[k].lc, a, Tree[k].lc, val);
    Update(k);
}
inline void Merge(int &k, int a, int b) {
    if(!a || !b) { k = a + b; return ; }
    if(Tree[a].rad <= Tree[b].rad) k = a, Tree[b].fa = a, Merge(Tree[k].rc, Tree[k].rc, b);
    else k = b, Tree[a].fa = b, Merge(Tree[k].lc, a, Tree[k].lc);
    Update(k);
}
inline void Insert(int &k, int c) {
    int a, b;
    Split(k, a, b, Tree[c].val);
    Tree[a].fa = a, Tree[b].fa = b;
    Merge(a, a, c), Merge(k, a, b);
}
inline int Get_Val(int k, int x) {
    while(Tree[Tree[k].lc].siz + 1 != x) {
        if(Tree[Tree[k].lc].siz >= x) k = Tree[k].lc;
        else x -= (Tree[Tree[k].lc].siz + 1), k = Tree[k].rc;
    }
    return p[Tree[k].val];
}
inline int Find(int x) {
    if(Tree[x].fa != x) return Tree[x].fa = Find(Tree[x].fa);
    return Tree[x].fa;
}
inline int Unnion(int f1, int f2) {
    f1 = Find(f1), f2= Find(f2);
    if(f1 != f2) Tree[f2].fa = f1;
}
inline void Search(int &x, int now) {
    if(!now) return ;
    Search(x, Tree[now].lc), Search(x, Tree[now].rc);
    Tree[now].lc = Tree[now].rc = 0, Tree[now].siz = 1;
    Insert(x, now);
    Tree[now].fa = x;
}
inline void Add_New(int u, int v) {
    if(Tree[u].siz < Tree[v].siz) swap(u, v);
    Search(u, v);
}
int main() {
    n = read(), m = read();
    for(register int i = 1, x; i <= n; ++i) { x = read(), Add(x), p[x] = i; }
    for(register int i = 1; i <= m; ++i) {
        int u = Find(read()), v = Find(read());
        Add_New(u, v);
    }
    q = read(); char c;
    for(register int i = 1; i <= q; ++i) {
        while(!isalpha(c = getchar()));
        int x = read(), y = read();
        if(c == 'Q') {
            x = Find(x);
            if(y > Tree[x].siz) { printf("-1\n"); continue; }
            printf("%d\n", Get_Val(x, y));
        }
        else {
            x = Find(x), y = Find(y);
            if(x != y) Add_New(x, y);
        }
    }
    return 0;
}

$(2)$ 思考与总结

很少见的平衡树合并思想，值得积累

另外很多关于合并的算法都能用 $dsu$ 优化，算是一个很常用的技巧

包括近期特别流行的 $dsu\ on\ a\ tree$ （过两天会写个 $blog$ ，还在学）

$4^o$ P4146 序列终结者

题面

$(1)$ 分析

看到翻转操作，很容易想到平衡树解决

考虑操作 $1, 3$ 如何实现

对于操作 $1$

考虑借用实现翻转操作的技巧，先将区间 $Split$ 出来，打上一个 $+val$ 的标记，在 $Split$ 和 $Merge$ 时 $Push\_Down$ 。

下传时要注意，左右儿子的 $tag$ ， $val$ ， $maxx$ （待会会提到）都要修改

对于操作 $3$

首先想到可以用 $Find\_Val$ 操作

可我们为了实现翻转操作， $Split$ 时是按 $siz$ 为关键字的，这样会导致满足 $BST$ 的并不是 $val$

考虑其他办法统计。

因为这时 $Split$ 可以划分出区间，所以我们可以考虑在 $Split$ 的同时将这个区间的 $maxx$ 求出。

那么在 $Push\_Up$ 的时候统计即可，注意 $Push\_Down$ 时也要更新这个值。

细节：

当左右儿子为空时，不能对 $maxx$ 进行更新，因为 $val$ 可能为负

代码：

//The code is from dxbdly
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e5 + 5, base = 13333, INF = 1e9 + 7;
int n, m, tot, root, res = 1;
struct node {
    int lc, rc, fa;
    int val, rad, siz, tag1, tag2, maxx;
}Tree[maxn];
inline int Rand() {
    res *= base; return res;
}
inline int Add(int val) {
    tot++, Tree[tot].lc = Tree[tot].rc = Tree[tot].tag1 = Tree[tot].tag2 = 0, Tree[tot].maxx = -INF;
    Tree[tot].val = val, Tree[tot].rad = Rand(), Tree[tot].siz = 1, Tree[tot].fa = tot;
    return tot;
}
inline void Push_Up(int k) { 
    Tree[k].siz = Tree[Tree[k].lc].siz + Tree[Tree[k].rc].siz + 1;
    Tree[k].maxx = Tree[k].val;
    if(Tree[k].lc) Tree[k].maxx = max(Tree[k].maxx, Tree[Tree[k].lc].maxx);
    if(Tree[k].rc) Tree[k].maxx = max(Tree[k].maxx, Tree[Tree[k].rc].maxx);
}
inline void Push_Down(int k) {
    if(Tree[k].tag2) {
        if(Tree[k].lc) Tree[Tree[k].lc].tag2 += Tree[k].tag2, Tree[Tree[k].lc].val += Tree[k].tag2, Tree[Tree[k].lc].maxx += Tree[k].tag2;
        if(Tree[k].rc) Tree[Tree[k].rc].tag2 += Tree[k].tag2, Tree[Tree[k].rc].val += Tree[k].tag2, Tree[Tree[k].rc].maxx += Tree[k].tag2;
        Tree[k].tag2 = 0;
    }
    if(Tree[k].tag1) {
        Tree[Tree[k].lc].tag1 ^= 1, Tree[Tree[k].rc].tag1 ^= 1;
        Tree[k].tag1 = 0, swap(Tree[k].lc, Tree[k].rc);
    }
}
inline void Split(int k, int &a, int &b, int val) {
    if(!k) { a = 0, b = 0; return ; }
    Push_Down(k);
    if(Tree[Tree[k].lc].siz + 1 <= val) a = k, Split(Tree[k].rc, Tree[k].rc, b, val - Tree[Tree[k].lc].siz - 1);
    else b = k, Split(Tree[k].lc, a, Tree[k].lc, val);
    Push_Up(k);
}
inline void Merge(int &k, int a, int b) {
    if(!a || !b) { k = a + b; return ; }
    if(Tree[a].rad <= Tree[b].rad) Push_Down(a), k = a, Tree[b].fa = a, Merge(Tree[k].rc, Tree[k].rc, b);
    else Push_Down(b), k = b, Tree[a].fa = b, Merge(Tree[k].lc, a, Tree[k].lc);
    Push_Up(k);
}
inline void Insert(int &k, int val) {
    int a, b, c = Add(val);
    Split(k, a, b, val), Merge(a, a, c), Merge(k, a, b);
}
inline void Update1(int &k, int l, int r) {
    int a, b, c;
    Split(k, a, c, r), Split(a, a, b, l - 1), Tree[b].tag1 ^= 1, Merge(a, a, b), Merge(k, a, c);
}
inline void Update2(int &k, int l, int r, int val) {
    int a, b, c;
    Split(k, a, c, r), Split(a, a, b, l - 1), Tree[b].tag2 += val, Tree[b].val += val, Merge(a, a, b), Merge(k, a, c);
}
inline void Query(int l, int r)  {
    int a, b, c;
    Split(root, a, c, r), Split(a, a, b, l - 1);
    printf("%lld\n", Tree[b].maxx);
    Merge(a, a, b), Merge(root, a, c);
}
signed main() {
    n = read(), m = read(), Tree[root].maxx = -INF;
    for(register int i = 1; i <= n; ++i) Insert(root, 0);
    for(register int i = 1; i <= m; ++i) {
        int op = read(), l = read(), r = read(), val;
        if(op == 1) val = read(), Update2(root, l, r, val);
        if(op == 2) Update1(root, l, r);
        if(op == 3) Query(l, r);
    }
    return 0;
}

$(2)$ 思考与总结

在使用平衡树处理区间操作时

考虑先打上标记，然后在 $Split$ 和 $Merge$ 时 $Push\_Down$ 是个很好的思路

同时也让我们看到了平衡树求区间最值的另一种方式。

$5.$ $The\ End$

总的来说， $FHQ-Treap$ 是一种比较全面的平衡树

它代码量短，同时功能多，可实现 $Splay$ 的翻转操作，也可以用来维护 $LCT$

其 $Split$ 操作的多种方式更是给它的应用增添了更多可能

这也告诫我们，学习数据结构应该深入的研究它与其它数据结构之间的区别，了解它独特的性质及用法，才是最重要的

希望本文能给大家带来帮助，感谢观看。

图片引自博客

本文作者 $\operatorname{dxbdly}$ ，转载或引用请加上原文链接

FHQ-Treap

1. 前言

2. Treap 的思想

3. FHQ-Treap 的思想与操作

1^o Add 操作

2^o Update 操作

3^o Merge 操作

4^o Split 操作

(1) 按权值分裂：

(2) 根据 siz 分裂:

5^o Insert 操作

6^o Delte 操作

7^o Find\_Val 操作

8^o Find\_rank 操作

9^o Find\_pre 操作

10^o Find\_Nex操作

11^o 常数优化 —— Rand

4. FHQ-Treap 的区间翻转

5. 例题

1^o HNOI2002 营业额统计

(1) 分析

(2) 思考与总结

2^o TJOI2007 书架

(1) 分析

(2) 思考与总结

3^o HNOI2012 永无乡

(1) 分析

(2) 思考与总结

4^o P4146 序列终结者

(1) 分析

(2) 思考与总结

5. The\ End

Q.E.D

内容目录

选择主题

$1.$ 前言

$2.$ $Treap$ 的思想

$3.$ $FHQ-Treap$ 的思想与操作

$1^o$ $Add$ 操作

$2^o$ $Update$ 操作

$3^o$ $Merge$ 操作

$4^o$ $Split$ 操作

$(1)$ 按权值分裂：

$(2)$ 根据 $siz$ 分裂:

$5^o$ $Insert$ 操作

$6^o$ $Delte$ 操作

$7^o$ $Find\_Val$ 操作

$8^o$ $Find\_rank$ 操作

$9^o$ $Find\_pre$ 操作

$10^o$ $Find\_Nex$ 操作

$11^o$ 常数优化 —— $Rand$

$4.$ $FHQ-Treap$ 的区间翻转

$5.$ 例题

$1^o$ HNOI2002 营业额统计

$(1)$ 分析

$(2)$ 思考与总结

$2^o$ TJOI2007 书架

$(1)$ 分析

$(2)$ 思考与总结

$3^o$ HNOI2012 永无乡

$(1)$ 分析

$(2)$ 思考与总结

$4^o$ P4146 序列终结者

$(1)$ 分析

$(2)$ 思考与总结

$5.$ $The\ End$

$Q.E.D$