可持久化左偏树（可持久化可并堆）
<pre><code class="language-cpp">#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int val[20*maxn]; //原序列
int ch[20*maxn][3], fa[20*maxn], dis[20*maxn] = {-1};
int root; //堆的根，等于0表示堆的空的，一个堆有一个根
int cnt;
inline int merge(int x, int y){//合并两个堆
if(x == 0) return y;
if(y == 0) return x;
if(val[x] > val[y]) swap(x, y);
val[++cnt] = val[x];
ch[cnt][0] = ch[x][0], ch[cnt][1] = ch[x][1];
fa[cnt] = fa[x], dis[cnt] = dis[x];
ch[cnt][1] = merge(ch[cnt][1], y);
fa[ch[cnt][1]] = cnt;
if(dis[ch[cnt][0]] < dis[ch[cnt][1]]) swap(ch[cnt][0], ch[cnt][1]);
dis[cnt] = dis[ch[cnt][1]] + 1;
return cnt;
}
int n, m;
int main(){
scanf("%d", &n);
cnt = n;//注意这一步
for(int i = 1; i <=n; i++){
scanf("%d", &val[i]);
// root = merge(root, i);
}
root = merge(root, 2);
root = merge(root, 3);
int tiit = 0;
tiit = merge(tiit, 4);
tiit = merge(tiit, 5);
int zooz = merge(tiit, root);
cout << val[root] << endl;
cout << val[tiit] << endl;
merge(zooz, 1);//没有覆盖老根
cout << val[zooz];
}</code></pre>