P3377

Aryper · 2021-08-18 10:53:25 · 个人记录

【模板】左偏树（可并堆）

左偏树入门。

性质：

1. 堆性质，根节点小于左右儿子的权值。

2. 左偏性质，定义每个节点的距离，维护对于每个节点，其左儿子的距离大于等于右儿子的距离。

3. 其本身的距离为右儿子的距离加一。

推论：n\ge 2^{k+1}-1\Rightarrow n+1\ge2^{k+1}\Rightarrow \log_2(n+1)\ge k+1\Rightarrow \log_2(n+1)-1\ge k

这个时用来保证时间复杂度的。

然后就是几个操作。

第一个是合并操作。

我们假设两个堆的堆顶分别为 x，y，然后我们令 x 的权值小于 y 的权值，那这样的话，x 就是新堆的堆顶，y 与 x 的右子树进行合并即可。

合并之后，而分别维护左偏性质（不符合就交换左右子树），以及节点距离为右儿子距离加一（直接操作即可，不影响维护）。

至此完成合并。

第二个操作是删除。我们将删除的节点（堆顶）做上标记，然后将左右子树合并即可。因为这里采用了路径压缩保证接近 O(\log n) 的复杂度，所以说删掉的节点仍需将其根节点指向合并后的堆顶（某些没有维护到的节点其堆顶仍指向已被删除的节点，故因如此操作）。

第三个操作是查询堆顶。我们这里采用存储堆顶的方式解决，使用到路径压缩。

所有操作的复杂度均为 O(\log n)。故总时间复杂度 O(m\log n)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,m,op,x,y;

struct LH{
  ll dis[N+5],val[N+5],rs[N+5],ls[N+5],rt[N+5];
  inline ll Merge(ll x,ll y) {
    if(!x||!y) return x+y;
    if(val[x]>val[y]||(val[x]==val[y]&&x>y)) swap(x,y);
    rs[x]=Merge(rs[x],y);if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
    rt[ls[x]]=rt[rs[x]]=rt[x]=x;dis[x]=dis[rs[x]]+1;return x;
  }
  inline ll Get(ll x) {return rt[x]==x?x:rt[x]=Get(rt[x]);}
  inline void Pop(ll x) {
    val[x]=-1;rt[ls[x]]=ls[x];rt[rs[x]]=rs[x];rt[x]=Merge(ls[x],rs[x]);
  }
}S;

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
  while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar('-');do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {write(x);putchar('\n');}

int main() {

  n=read();m=read();

  for(ll i=1;i<=n;i++) {S.rt[i]=i;S.val[i]=read();}

  for(ll i=1;i<=m;i++) {
    op=read();x=read();
    if(op==1) {
      y=read();if(S.val[x]==-1||S.val[y]==-1) continue;
      ll f1=S.Get(x),f2=S.Get(y);
      if(f1!=f2) S.rt[f1]=S.rt[f2]=S.Merge(f1,f2);
    }
    if(op==2) {
      if(S.val[x]==-1) {writeln(-1);}
      else {writeln(S.val[S.Get(x)]);S.Pop(S.Get(x));}
    }
  }

  return 0;
}