笔记——左偏树

作用

支持删除,合并,查询最大或最小值（还可以查询中位数哦）

单次时间复杂度\(O(log n)\)

基本概念

• 堆：二叉树

• 空节点: 无左儿子的节点

• 大根堆: 具有每个节点都满足该节点的权值大于等于她的儿子节点的堆

• 小根堆: 与大根堆 相反的堆

• 节点的距离: 走右儿子直到空节点为止浏览过的节点数

• 左偏树: 左儿子的距离大于等于右儿子距离的堆

性质

• 是一个大（小）跟堆

• 左儿子的距离大于等于右儿子距离

• 节点的距离 等于该节点右儿子的距离 + 1（太水 不解释）

• 一个有n个节点的左偏树她的\(root\)的距离不超过为\(log(n+1)-1\)

由最后一个性质 保证一次到堆底的时间复杂度为\(log\)级

实现

\(merge\)

只需要学会\(merge\) 其她就很简单了

\(merge\)就是将两个堆合并

inline int merge(int u,int v)
    {
        if(!u||!v) return u | v;
        至少有一个是0 返回另一个 等效于u+v
        if(heap[u].val > heap[v].val)
            swap(u,v);

        heap[u].r = merge(heap[u].r,v);
      合并
        if(dis[heap[u].l] < dis[heap[u].r])
            swap(heap[u].l,heap[u].r);
      满足性质2
        dis[u] = dis[heap[u].r] + 1;
      算距离（性质3）
        return u;
    }

好了其实现在你已经可以\(A\)这道题了

\(delete\)

删除一个节点 等价于 合并这个节点的左右子树

查询最大最小值

每一颗左偏树 只能维护最大最小值中的一个

由性质1得 堆的最大最小值为根的权值

并查集

第x个数和第y个数所在的小根堆合并

这句活用并查集实现

注意要路径压缩

\(Code\)

板子题

#include <cstdio>
#include <iostream>
#define reg register int
using namespace std;
const int MAXN = 100005;
int n,m;
namespace leftist_tree
{
    struct node {int l,r,val;};
    node heap[MAXN];
    bool exist[MAXN];
    int dis[MAXN],rt[MAXN];
    inline void init()
    {
        for(reg i = 1;i <= n;i++)
            scanf("%d",&heap[i].val),rt[i] = i;
    }
    inline int merge(int u,int v)
    {
        if(!u||!v) return u | v;
        if(heap[u].val > heap[v].val)
            swap(u,v);
        heap[u].r = merge(heap[u].r,v);
        if(dis[heap[u].l] < dis[heap[u].r])
            swap(heap[u].l,heap[u].r);
        dis[u] = dis[heap[u].r] + 1;
        return u;
    }
    inline int find_set(int x)
    {
        if(rt[x] == x) return x;
        return rt[x] = find_set(rt[x]);
    }
}
using namespace leftist_tree;
int main()
{
    scanf("%d%d",&n,&m);
    leftist_tree::init();
    while(m--)
    {
        int sit;
        scanf("%d",&sit);
        if(sit & 1)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            if(exist[u]||exist[v]) continue;
            int fu = find_set(u),fv = find_set(v);
            if(fu != fv) rt[fu] = rt[fv] = merge(fu,fv);
        } else {
            int x;
            scanf("%d",&x);
            if(exist[x])
            {
                printf("-1\n");
                continue;
            }
            x = find_set(x);
            printf("%d\n",heap[x].val);
            exist[x] = 1;
            rt[heap[x].l] = rt[heap[x].r] = rt[x] = merge(heap[x].l,heap[x].r);
            heap[x].l = heap[x].r = dis[x] = 0;
        }
    }
    return 0;
}

稍微难一点的板子题

提升一下:

分成多个不下降的子序列，求出每个子序列的中位数

对于连续上升的子序列的中位数

我们把她合并为一个堆 再求中位数

求中位数

一个堆的中位数等于根的权值的充要条件就是

这个堆只有我们要求得堆的大小的一半（此时此堆仍是大（小）根堆）

稍微想一下应该就可以理解了吧QAQ

\(Code\)

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define reg register int
const int MAXN = 1e6 + 10;
typedef long long ll;
int n,num[MAXN],son[MAXN][2];
template<typename T>
inline T Read(T x)
{
    x = 0;
    int f = 1;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
    while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
    return x * f;
}
namespace leftist_tree {
    struct node {
        int size,lef,rig,val,rt;
    };
    node heap[MAXN];
    int dis[MAXN];
    inline int merge(int u,int v) {
        if(!u||!v) return u | v;
        if(num[u] < num[v]||(num[u] == num[v]&&v > u)) swap(u,v);
        son[u][1] = merge(son[u][1],v);
        if(dis[son[u][0]] < dis[son[u][1]]) swap(son[u][0],son[u][1]);
        dis[u] = dis[son[u][1]] + 1;
        return u;
    }
}
using namespace leftist_tree;
inline void init() {
    n = Read(1);
    dis[0] = -1;
    memset(heap,0,sizeof(heap));
    for(reg i = 1; i <= n; i++)
    {
        num[i] = Read(1) - i;
    }
}
int cnt,b[MAXN];
ll ans;
inline void solve() {
    for(reg i = 1; i <= n; i++) {
        heap[++cnt] = (node){1,i,i,num[i],i};
        while(cnt > 1&&heap[cnt - 1].val > heap[cnt].val) {
        对于连续上升的子序列的中位数

            我们把她合并为一个堆 再求中位数
            cnt--;
            heap[cnt].rt = merge(heap[cnt].rt,heap[cnt + 1].rt);
            heap[cnt].size += heap[cnt + 1].size;
            heap[cnt].rig = heap[cnt + 1].rig;
            while(heap[cnt].size * 2 > heap[cnt].rig - heap[cnt].lef + 2) {
                heap[cnt].size--;
                heap[cnt].rt = merge(son[heap[cnt].rt][0],son[heap[cnt].rt][1]);
            }
          只保留一半元素
            heap[cnt].val = num[heap[cnt].rt];
        }
    }
    for(reg i = 1; i <= cnt; i++)
        for(reg j = heap[i].lef; j <= heap[i].rig; j++) {
            b[j] = heap[i].val;
            ans += 1ll * abs(b[j] - num[j]);
        }
    printf("%lld\n",ans);
}
int main() {
    init();
    solve();
    return 0;
}