ACM模板库

ACM模板库


可持久化左偏树(可持久化可并堆)

#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];
}

页面列表

ITEM_HTML