首页 > 其他分享 >左偏树/可并堆

左偏树/可并堆

时间：2023-11-07 13:47:38浏览次数：32  
标签：ch lc int ll fa rc 左偏

20231107

左偏树/可并堆

将左偏树/可并堆做一个小结，

不写我可能就要忘了。。。

左偏树，顾名思义，就是保证左子树深度一定大于右子树，同时需要满足堆的性质，

于是在合并两个堆的时候的时间复杂度就为 \(\log n\) ,

感觉是非常易懂的，具体实现的细节还是有一些。

注意我们会用到并查集和 merge 函数，

每一次合并一定是合并到右儿子，因为这样可以尽可能保证树的左右子树是相对平衡的，

从而可以大大减小时间复杂度。

具体的 merge 代码如下：

int merge(int x,int y){
  if(!x||!y) return x+y;
  if(a[y]<a[x]) swap(x,y);
  rc[x]=merge(rc[x],y); 
  if(dep[lc[x]]<dep[rc[x]]) swap(lc[x],rc[x]);
  dep[x]=dep[rc[x]]+1;
  return x;
}

还是比较易懂吧。主要就是想降低深度，

合并 \(n\) 大小的堆和 \(m\) 大小的堆的均摊复杂度是 \(O(\log n+\log m)\)。

P3377 【模板】左偏树/可并堆

传送门

模板题。

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,m,fa[N],lc[N],rc[N],dep[N];
bool fl[N];
struct node{
  int val,id;
  bool operator <(const node &rhs) const{
    if(val!=rhs.val) return val<rhs.val;
    return id<rhs.id;
  } 
}a[N];

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

int find(int x){
  if(fa[x]==x) return x;
  return fa[x]=find(fa[x]);
}

int merge(int x,int y){
  if(!x||!y) return x+y;
  if(a[y]<a[x]) swap(x,y);
  rc[x]=merge(rc[x],y); 
  if(dep[lc[x]]<dep[rc[x]]) swap(lc[x],rc[x]);
  dep[x]=dep[rc[x]]+1;
  return x;
}

int main(){
  /*2023.10.30 H_W_Y P3377 【模板】左偏树/可并堆 */
  dep[0]=-1;n=read();m=read();
  for(int i=1;i<=n;i++) a[i].val=read(),fa[i]=i,a[i].id=i;
  for(int i=1;i<=m;i++){
  	int op=read(),x=read();
  	if(op==1){
  	  int y=read();
	  if(fl[x]||fl[y]) continue;
	  x=find(x);y=find(y);
	  fa[x]=fa[y]=merge(x,y);	
	}
	else {
	  if(fl[x]){puts("-1");continue;}
	  x=find(x);
	  printf("%d\n",a[x].val);
	  fl[x]=true;fa[lc[x]]=fa[rc[x]]=fa[x]=merge(lc[x],rc[x]);
	  lc[x]=rc[x]=dep[x]=0;
	}
  }
  return 0;
}

注意删除一个数的时候的操作。

P1456 Monkey King

传送门

还是模板题，删除和合并的时候一定要记录好每一个堆的根是哪一个，否则很容易搞混。

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,m,lc[N],rc[N],dep[N],fa[N],a[N];

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f; 
}

int find(int x){
  if(fa[x]==x) return x;
  return fa[x]=find(fa[x]);
}

int merge(int x,int y){
  if(!x||!y) return x+y;
  if(a[x]<a[y]) swap(x,y);
  rc[x]=merge(rc[x],y);
  if(dep[lc[x]]<dep[rc[x]]) swap(lc[x],rc[x]);
  dep[x]=dep[rc[x]]+1;
  return x;
}

int main(){
  /*2023.10.30 H_W_Y P1456 Monkey King 左偏树*/ 
  while(scanf("%d",&n)!=EOF){
  	for(int i=1;i<=n;i++) a[i]=read(),fa[i]=i,lc[i]=rc[i]=dep[i]=0;
  	m=read();
  	for(int i=1;i<=m;i++){
  	  int x=read(),y=read(),rt,art,brt;
	  x=find(x),y=find(y);
	  if(x==y){puts("-1");continue;}
	  a[x]>>=1;
	  rt=merge(lc[x],rc[x]);
	  lc[x]=rc[x]=dep[x]=0;
	  art=merge(rt,x);
	  fa[rt]=fa[x]=art;
	  a[y]>>=1;
	  rt=merge(lc[y],rc[y]);
	  lc[y]=rc[y]=dep[y]=0;
	  brt=merge(rt,y);
	  fa[rt]=fa[y]=brt;
	  rt=merge(art,brt);
	  fa[art]=fa[brt]=rt;
	  printf("%d\n",a[rt]);	
	}
  }
  return 0;
}

P2713 罗马游戏

传送门

继续模板题。

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int n,m,a[N],fa[N],lc[N],rc[N],dep[N];
bool fl[N];

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

int find(int x){
  if(fa[x]==x) return x;
  return fa[x]=find(fa[x]);
}

int merge(int x,int y){
  if(!x||!y) return x+y;
  if(a[x]>a[y]) swap(x,y);
  rc[x]=merge(rc[x],y);
  if(dep[rc[x]]>dep[lc[x]]) swap(lc[x],rc[x]);
  dep[x]=dep[rc[x]]+1;
  return x;
}

int main(){
  /*2023.10.30 H_W_Y P2713 罗马游戏 左偏树*/ 
  n=read();
  for(int i=1;i<=n;i++) a[i]=read(),fa[i]=i;
  m=read();
  for(int i=1;i<=m;i++){
  	char ch=getchar();
  	while(ch!='M'&&ch!='K') ch=getchar();
	int x=read();
	if(ch=='M'){
	  int y=read();
	  if(fl[x]||fl[y]) continue;
	  x=find(x);y=find(y);
	  if(x==y) continue;
	  fa[x]=fa[y]=merge(x,y); 
	} 
	else {
	  if(fl[x]){puts("0");continue;}
	  x=find(x);
	  fl[x]=true;printf("%d\n",a[x]);
	  fa[lc[x]]=fa[rc[x]]=fa[x]=merge(lc[x],rc[x]);
	  lc[x]=rc[x]=dep[x]=0;
	}
  } 
  return 0;
}

P1552 [APIO2012] 派遣

传送门

加难度了。

感觉很抽象，想到了对于每一个节点去建立一个左偏树，

但是总感觉 LCA 不一定要是这个点，但是发现题目中是只要是父亲就行了——这下这下了。

于是就直接维护最大的不断合并就可以了，如果整棵树的 \(sum\) 超了，就直接把顶部的删除就可以了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=1e5+5;
int n,fa[N],siz[N],lc[N],rt=0,rc[N],dep[N];
ll sum[N],ans=0,m;
struct node{
  int fa,c,l;
}a[N];
vector<int> g[N];

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

int find(int x){
  if(fa[x]==x) return x;
  return fa[x]=find(fa[x]);
}

int merge(int x,int y){
  if(!x||!y) return x+y;
  if(a[x].c<a[y].c) swap(x,y);
  rc[x]=merge(rc[x],y);
  if(dep[rc[x]]>dep[lc[x]]) swap(lc[x],rc[x]);
  dep[x]=dep[rc[x]]+1;
  sum[x]=sum[lc[x]]+sum[rc[x]]+1ll*a[x].c;
  siz[x]=siz[lc[x]]+siz[rc[x]]+1;
  return x;
}

void dfs(int u){
  for(auto v:g[u]){
  	dfs(v);
  	int x=find(u),y=find(v);
  	fa[x]=fa[y]=merge(x,y);
  }
  while(sum[find(u)]>m){
  	int x=find(u);
  	fa[lc[x]]=fa[rc[x]]=fa[x]=merge(lc[x],rc[x]);
  	dep[x]=sum[x]=siz[x]=0;
  }
  ans=max(ans,1ll*siz[find(u)]*a[u].l);
}

int main(){
  /*2023.11.7 H_W_Y P1552 [APIO2012] 派遣 左偏树*/ 
  n=read();m=1ll*read();
  for(int i=1;i<=n;i++){
  	a[i].fa=read();a[i].c=read();a[i].l=read();
  	fa[i]=i;siz[i]=1;sum[i]=a[i].c;dep[i]=1;
  	if(a[i].fa==0) rt=i;
  	else g[a[i].fa].pb(i);
  }
  dfs(rt);
  printf("%lld\n",ans);
  return 0;
}

P3261 [JLOI2015] 城池攻占-一个堆修改

传送门

其实就是左偏树的过程中多了一个标记的 pushdown，

一定要在每一个地方都要 pd，且乘法标记的初始值是 \(-1\)。

还调了挺久，记得在删除一个元素的时候要 pd！！！

有些时候静态查错还是很有效果的。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=3e5+5;
int n,m,rt[N],lc[N],rc[N],dep[N],dis[N],ans[N];
struct tree{
  ll h,tag;
  int vis,fa;
}t[N];
struct node{
  ll val,tag1,tag2;
  int ans,st;
}a[N];

ll read(){
  ll x=0,f=1ll;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f; 
}

void change(int x,int vis,ll tag){
  if(vis==1) a[x].val+=tag,a[x].tag1+=tag;
  else a[x].tag1*=tag,a[x].tag2*=tag,a[x].val*=tag;
}

void pd(int x){
  if(lc[x])
    change(lc[x],2,a[x].tag2),
    change(lc[x],1,a[x].tag1);
  if(rc[x]) 
    change(rc[x],2,a[x].tag2),
	change(rc[x],1,a[x].tag1);
  a[x].tag1=0;a[x].tag2=1ll;
}

int merge(int x,int y){
  if(!x||!y) return x+y;
  pd(x);pd(y);
  if(a[x].val>a[y].val) swap(x,y);
  rc[x]=merge(rc[x],y);
  if(dep[lc[x]]<dep[rc[x]]) swap(lc[x],rc[x]);
  dep[x]=dep[rc[x]]+1;
  return x; 
}

void print(int x){
  int p[15],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x) p[++tmp]=x%10,x/=10;
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar('\n');
}

int main(){
  /*2023.11.7 H_W_Y P3261 [JLOI2015] 城池攻占 左偏树*/ 
  n=(int)read(),m=(int)read();dis[0]=-1;
  for(int i=1;i<=n;i++) t[i].h=read(),rt[i]=0;
  for(int i=2;i<=n;i++){
  	t[i].fa=(int)read(),t[i].vis=(int)read()+1,t[i].tag=read();
	dis[i]=dis[t[i].fa]+1;
  }
  for(int i=1;i<=m;i++) a[i].val=read(),a[i].st=(int)read(),dep[i]=1,a[i].tag2=1ll;
  for(int i=1;i<=m;i++) rt[a[i].st]=merge(rt[a[i].st],i);
  
  for(int u=n;u>=1;u--){
    while(rt[u]&&a[rt[u]].val<t[u].h){
  	  int x=rt[u];a[x].ans=u;
  	  ans[u]++;pd(x);
  	  rt[u]=merge(lc[x],rc[x]);
    }
    if(!rt[u]||u==1) continue;
    change(rt[u],t[u].vis,t[u].tag);
    rt[t[u].fa]=merge(rt[t[u].fa],rt[u]);
  }
  
  for(int i=1;i<=n;i++) print(ans[i]);
  for(int i=1;i<=m;i++) print(dis[a[i].st]-dis[a[i].ans]);
  return 0;
}

注意 find(0) 是会出现 MLE/RE 的奇妙错误。

P4971 断罪者-单点修改（不一定是堆顶）

传送门

这道题主要是关于不是堆顶的数如何修改。

这个时候要特别注意，建议把 fa 的改变复制算在 merge 里面去完成。

于是修改这个数的过程就是这个样子的：

int merge(int x,int y){
  if(!x||!y) return x+y;
  if(a[x]<a[y]) swap(x,y);
  rc[x]=merge(rc[x],y);
  if(dep[lc[x]]<dep[rc[x]]) swap(lc[x],rc[x]);
  fa[x]=fa[lc[x]]=fa[rc[x]]=x;
  dep[x]=dep[rc[x]]+1;
  return x;
}

void rebuild(int x){
  int l=lc[x],r=rc[x];
  fa[l]=l;fa[r]=r;
  lc[x]=rc[x]=dep[x]=0;
  merge(find(x),merge(l,r));
}

于是主函数写起来就是比较简单的。

一定不要 find(0) ，会一直 MLE。。。

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N=2e6+5;
int T,W,n,m,fa[N],dep[N],lc[N],rc[N];
ll K,sum,mx;
struct node{
  ll val;
  int id;
  bool operator <(const node &rhs) const{
    if(val!=rhs.val) return val<rhs.val;
    return id>rhs.id;
  }
}a[N];
bool vis[N];

ll read(){
  ll x=0,f=1ll;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void print(ll x){
  int p[25],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x) p[++tmp]=x%10,x/=10;
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar('\n');
}

int find(int x){
  if(x==fa[x]) return x;
  return fa[x]=find(fa[x]);
}

int merge(int x,int y){
  if(!x||!y) return x+y;
  if(a[x]<a[y]) swap(x,y);
  rc[x]=merge(rc[x],y);
  if(dep[lc[x]]<dep[rc[x]]) swap(lc[x],rc[x]);
  fa[x]=fa[lc[x]]=fa[rc[x]]=x;
  dep[x]=dep[rc[x]]+1;
  return x;
}

void rebuild(int x){
  int l=lc[x],r=rc[x];
  fa[l]=l;fa[r]=r;
  lc[x]=rc[x]=dep[x]=0;
  merge(find(x),merge(l,r));
}

void sol(){
  n=(int)read();m=(int)read();
  for(int i=1;i<=n;i++) a[i].val=read(),a[i].id=i,fa[i]=i,lc[i]=rc[i]=dep[i]=0;
  fa[0]=dep[0]=lc[0]=rc[0]=0;
  memset(vis,false,sizeof(vis));
  for(int i=1;i<=m;i++){
  	int op=(int)read(),A=(int)read();
  	if(op==2){
  	  a[A].val=0;
      rebuild(A);
	}
	if(op==3){
	  ll B=read();int x=find(A);
	  a[x].val=a[x].val>B?a[x].val-B:0;
      rebuild(x);
	}
	if(op==4){
	  int B=(int)read();
	  int x=find(A),y=find(B);
	  if(x==y) continue;
	  merge(x,y);
	}
  }
  
  sum=0;mx=0;
  for(int i=1;i<=n;i++)
  	if(!vis[find(i)]) sum+=a[find(i)].val,mx=max(mx,a[find(i)].val),vis[find(i)]=true;
  if(W==2) sum-=mx;
  if(W==3) sum+=mx;
  if(sum==0) printf("Gensokyo ");
  else if(sum>K) printf("Hell ");
  else printf("Heaven ");
  print(sum);
}

int main(){
  /*2023.11.7 H_W_Y P4971 断罪者 左偏树*/ 
  T=(int)read();W=(int)read();K=read();
  while(T--) sol();
  return 0;
}

P3273 [SCOI2011] 棘手的操作-找不到家了

传送门

被列到题单里面，但是不太能左偏树——左偏树似乎会被卡。

于是我考虑了另外一种做法。

离线，按照某种规定重新排序之后去用线段树维护即可。

至于这个某种规定就是你把一个块里面的排在一起就行啦~

想还是挺好想的吧。

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N=3e5+5;
const ll inf=1e18;
int n,m,rev[N],id[N],fa[N],L[N],R[N],idx=0,nxt[N];
ll a[N];
struct query{
  int op,x,y;
  ll val;
}q[N];

ll read(){
  ll x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void print(ll x){
  int p[25],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x) p[++tmp]=x%10,x/=10;
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar('\n');
}

int find(int x){
  if(fa[x]==x) return x;
  return fa[x]=find(fa[x]);
}

void merge(int x,int y){
  x=find(x);y=find(y);
  if(x==y) return;
  nxt[R[x]]=L[y];
  R[x]=R[y];fa[y]=x;
  return;
}

struct sgt{
  ll tag,mx;
}tr[N<<2];

#define mid ((l+r)>>1)
#define lc p<<1
#define rc p<<1|1
#define lson l,mid,lc
#define rson mid+1,r,rc

void pu(int p){tr[p].mx=max(tr[lc].mx,tr[rc].mx);}

void pd(int p){
  if(!tr[p].tag) return;
  tr[lc].tag+=tr[p].tag;
  tr[rc].tag+=tr[p].tag;
  tr[lc].mx+=tr[p].tag;
  tr[rc].mx+=tr[p].tag;
  tr[p].tag=0;
}

void build(int l,int r,int p){
  if(l==r) return tr[p].mx=a[id[l]],void();
  build(lson);build(rson);pu(p); 
}

void upd(int l,int r,int p,int x,int y,ll val){
  if(x<=l&&y>=r){
  	tr[p].tag+=val;
  	tr[p].mx+=val;
  	return ;
  }
  pd(p);
  if(x<=mid) upd(lson,x,y,val);
  if(y>mid) upd(rson,x,y,val);
  pu(p);
}

ll qry(int l,int r,int p,int x,int y){
  if(x<=l&&y>=r) return tr[p].mx;
  pd(p);ll res=-inf;
  if(x<=mid) res=max(res,qry(lson,x,y));
  if(y>mid) res=max(res,qry(rson,x,y));
  return res;
}

void sol(){
  n=(int)read();
  for(int i=1;i<=n;i++) a[i]=read(),L[i]=R[i]=fa[i]=i,nxt[i]=0;
  m=(int)read();
  for(int i=1;i<=m;i++){
    char ch=getchar(),s;
    while(ch!='A'&&ch!='U'&&ch!='F') ch=getchar(); 
    if(ch=='U'){
      int x=(int)read(),y=(int)read();
      merge(x,y);
      q[i].x=x;q[i].y=y;q[i].op=1;
	}
	if(ch=='A'){
      s=getchar();
      if(s=='1') q[i].op=2,q[i].x=(int)read(),q[i].val=read();
	  if(s=='2') q[i].op=3,q[i].x=(int)read(),q[i].val=read();
	  if(s=='3') q[i].op=4,q[i].val=read();
	}
	if(ch=='F'){
	  s=getchar();
	  if(s=='1') q[i].op=5,q[i].x=(int)read();
	  if(s=='2') q[i].op=6,q[i].x=(int)read();
	  if(s=='3') q[i].op=7;
	}
  }
  idx=0;
  for(int i=1;i<=n;i++)
  	if(find(i)==i){
  	  int nw=L[i];
	  while(nw){
	  	id[++idx]=nw;
	  	rev[nw]=idx;
	  	if(nw==R[i]) break;
	  	nw=nxt[nw];
	  }	
	}
  build(1,n,1);
  for(int i=1;i<=n;i++) L[i]=R[i]=fa[i]=i,nxt[i]=0;
  for(int i=1;i<=m;i++){
    if(q[i].op==1) merge(q[i].x,q[i].y);
    if(q[i].op==2) upd(1,n,1,rev[q[i].x],rev[q[i].x],q[i].val);
    if(q[i].op==3) upd(1,n,1,rev[L[find(q[i].x)]],rev[R[find(q[i].x)]],q[i].val);
    if(q[i].op==4) upd(1,n,1,1,n,q[i].val);
    if(q[i].op==5) print(qry(1,n,1,rev[q[i].x],rev[q[i].x]));
    if(q[i].op==6) print(qry(1,n,1,rev[L[find(q[i].x)]],rev[R[find(q[i].x)]]));
    if(q[i].op==7) print(tr[1].mx);
  }
}

int main(){
  /*2023.11.7 H_W_Y P3273 [SCOI2011] 棘手的操作 乱搞*/ 
  sol();return 0;
}

左偏树到此为止！

标签：ch,lc,int,ll,fa,rc,左偏
From： https://www.cnblogs.com/hwy0622/p/zuopianshu.html

相关文章

  • 数据结构——左偏树/可并堆学习笔记
    引入作为树形数据结构的一员——堆，对于取极值拥有着优秀的复杂度，但是，合并两个堆却成为了一个问题。除了朴素算法外，还有什么算法可以合并两个堆呢？正文那么，可并堆是个啥呢？简单来说，它是一个支持合并操作的二叉堆（好像是废话）。首先，简单介绍一下二叉堆的性质，学过的读者可自行跳过。......
  • 【学习笔记】左偏树
    左偏树属于可并堆的一种，可并堆，也就是可以在较低的时间复杂度下完成对两个堆的合并。定义及性质对于一棵二叉树，定义外节点为左儿子或右耳子为空的节点，定义其的\(dist\)为\(1\)，而不是外节点的\(dist\)为其到子树中最近的外节点距离\(+1\)。空节点的\(dist\)为\(0\)。例......
  • 左偏树
    模板： #include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e5+10;intn,m,heap[MAXN];intfa[MAXN],ls[MAXN],rs[MAXN],dis[MAXN];booldel[MAXN];intfind(intx){returnx==fa[x]?x:fa[x]=find(fa[x]);}intMerge(int......
  • 左偏树
    左偏树左偏树是一种可以让我们在\(O(\logn)\)的时间复杂度内进行合并的堆式数据结构。为了方便以下的左偏树为小根堆来讨论。定义外结点：左儿子或者右儿子是空节点的结点。距离：一个结点\(x\)的距离\(dis[x]\)定义为其子树中与结点\(x\)最近的外结点到\(x\)的距离......
  • 【P4331 [BalticOI 2004]】Sequence 数字序列 题解（左偏树维护动态区间中位数）
    左偏树维护动态区间中位数。传送门P4331BalticOI2004Sequence数字序列。Solution1我的思路和题解前半部分完全重合了（（如果按照单调不增去分割\(a\)序列的话，对于每一段我们能很简单地得出它的最佳答案：中位数。发现严格单调很难做，很难拿捏，考虑对\(a\)序列的每一项都进......
  • 左偏树学习笔记
    一、前言左偏树是一种可以在\(O(\logn)\)内快速合并的堆式数据结构。具体来说，插入一个元素：\(O(\logn)\)。查询最值：\(O(1)\)。删除最值：\(O(\logn)\)。合并：\(O(\logn)\)。减少一个元素的值：\(O(\logn)\)。同时它可以持久化。二、定义外节点：左儿子或者右儿子为空的......
  • 洛谷P1552 [APIO2012] 派遣 题解 左偏树
    题目链接：https://www.luogu.com.cn/problem/P1552题目大意：每次求子树中薪水和不超过\(M\)的最大节点数。解题思路：使用左偏树维护一个大根堆。首先定义一个Node的结构体：structNode{ints[2],c,sz,dis;longlongsum;Node(){};Node(int_c){s......
  • 洛谷 P3377 【模板】左偏树（可并堆）题解 左偏树模板题
    题目链接：https://www.luogu.com.cn/problem/P3377维护左偏树的同时还需要维护一个并查集。但是并查集也就一个find操作。pop的时候更新f[x]的操作很神奇。示例程序：#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+5;intn,m,op,x,y,val[m......
  • 【理论】左偏树笔记
    左偏树是可并堆的一种实现方法。左偏，很容易形象地理解它是什么意思。但对于一棵树，如何用形象和具体化的语言来描述左偏性质？考虑定义\(dis_i\)表示\(i\)的子树中最近......
  • 左偏树(可并堆)
    左偏树(可并堆)左偏树与配对堆一样，是一种可并堆，具有堆的性质，并且可以快速合并。一种\(O(\log_2n)\)内合并的数据结构。左偏树是一棵二叉树，它不仅具有堆的性质，并且是「左......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99