左偏树作业总结-平芜编程栈

左偏树

算法浅析

左偏树本质上是就是一个堆，不过在堆的基础上新增了 “左偏” 的性质，使得合并跟加快速.
思路上大致可以从 “合并" 的角度想起.

A - 可并堆 1

板题，直接上代码.

#include<bits/stdc++.h> # define Maxn 100005 using namespace std; bool bz[Maxn]; int n,m,op,x,y,v,tot; struct Node{int fa,dist,l,r,v;}tr[Maxn]; int find(int x) { if(x!=tr[x].fa) tr[x].fa=find(tr[x].fa); return tr[x].fa; } int Merge(int x,int y) { if((!x)||(!y)) return x+y; if(tr[x].v>tr[y].v) swap(x,y); tr[x].r=Merge(tr[x].r,y); if(tr[tr[x].l].dist<tr[tr[x].r].dist) swap(tr[x].l,tr[x].r); tr[x].dist=tr[tr[x].r].dist+1; return x; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&v); tr[++tot]={tot,0,0,0,v}; } while(m--) { scanf("%d",&op); if(op==1) { scanf("%d%d",&x,&y); if(bz[x]|bz[y]) continue; int f1=find(x),f2=find(y); if(f1==f2) continue; tr[f1].fa=tr[f2].fa=Merge(f1,f2); } if(op==2) { scanf("%d",&x); if(bz[x]) {printf("-1\n");continue;} int f1=find(x);bz[f1]=1; printf("%d\n",tr[f1].v); if((!tr[f1].l)&&(!tr[f1].r)) continue; tr[f1].fa=tr[tr[f1].l].fa=tr[tr[f1].r].fa=Merge(tr[f1].l,tr[f1].r); } } return 0; }

B - Monkey King

也是板题，不过要注意最后输出的是所有的最大。

#include<bits/stdc++.h> # define Maxn 100005 using namespace std; int n,m,v,x,y,tot,p[Maxn]; struct Node{int fa,l,r,dist,v,id;}tr[Maxn<<2]; int find(int x) { if(x!=tr[x].fa) tr[x].fa=find(tr[x].fa); return tr[x].fa; } int Merge(int x,int y) { if((!x)||(!y)) return x+y; if(tr[x].v<tr[y].v) swap(x,y); tr[x].r=Merge(tr[x].r,y); if(tr[tr[x].l].dist<tr[tr[x].r].dist) swap(tr[x].l,tr[x].r); tr[x].dist=tr[tr[x].r].dist+1; return x; } void clear() { for(int i=1;i<=tot;i++) tr[i]={0,0,0,0,0,0}; tot=0; } int main() { // freopen("my.out","w",stdout); while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) { scanf("%d",&v); tr[++tot]={i,0,0,0,v,i},p[i]=i; } scanf("%d",&m); while(m--) { scanf("%d%d",&x,&y); int f1=find(p[x]),f2=find(p[y]); if(f1==f2) {printf("-1\n");continue;} int newf1,newf2,Newf1,Newf2,RT; newf1=tr[f1].fa=tr[tr[f1].l].fa=tr[tr[f1].r].fa=Merge(tr[f1].l,tr[f1].r); tr[++tot]={tot,0,0,0,tr[f1].v/2,tr[f1].id},p[tr[f1].id]=tot; Newf1=tr[tot].fa=tr[newf1].fa=Merge(tot,newf1); newf2=tr[f2].fa=tr[tr[f2].l].fa=tr[tr[f2].r].fa=Merge(tr[f2].l,tr[f2].r); tr[++tot]={tot,0,0,0,tr[f2].v/2,tr[f2].id},p[tr[f2].id]=tot; Newf2=tr[tot].fa=tr[newf2].fa=Merge(tot,newf2); RT=tr[Newf1].fa=tr[Newf2].fa=Merge(Newf1,Newf2); printf("%d\n",tr[RT].v); }clear(); } return 0; }

C - 派遣

显然在领导固定时，人越多越好，于是考虑从小到大依次选择，然后删掉多余的.
显然可用左偏树实现. 每个点最多进堆一次，出堆一次，时间复杂度O(nlogn)O(nlogn)O(nlogn).

#include<bits/stdc++.h> # define Maxn 100005 # define ll long long using namespace std; int n,m,srt[Maxn],RT,cnt; int head[Maxn],tot=1; ll ans; struct Edge{int to,next;}e[Maxn]; struct Node{int fa,c,l;}a[Maxn]; struct Tree{int fa,l,r,dist,sz,v;ll sum;}tr[Maxn]; void add(int u,int v) { e[tot]={v,head[u]}; head[u]=tot++; } int find(int x) { if(x!=tr[x].fa) tr[x].fa=find(tr[x].fa); return tr[x].fa; } int Merge(int x,int y) { if((!x)||(!y)) return x+y; if(tr[x].v<tr[y].v) swap(x,y); tr[x].r=Merge(tr[x].r,y); if(tr[tr[x].l].dist<tr[tr[x].r].dist) swap(tr[x].l,tr[x].r); tr[x].dist=tr[tr[x].r].dist+1; tr[x].sz=tr[tr[x].l].sz+tr[tr[x].r].sz+1; tr[x].sum=tr[tr[x].l].sum+tr[tr[x].r].sum+tr[x].v; return x; } int Del(int x) { int rt=tr[x].fa=tr[tr[x].l].fa=tr[tr[x].r].fa=Merge(tr[x].l,tr[x].r); return rt; } void dfs(int rt) { for(int i=head[rt];i;i=e[i].next) { dfs(e[i].to); srt[rt]=tr[srt[rt]].fa=tr[srt[e[i].to]].fa=Merge(srt[rt],srt[e[i].to]); } while(tr[srt[rt]].sum>m) srt[rt]=Del(srt[rt]); // printf("%d: %d\n",rt,tr[srt[rt]].sz); ans=max(ans,1ll*a[rt].l*tr[srt[rt]].sz); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d%d",&a[i].fa,&a[i].c,&a[i].l); tr[++cnt]={cnt,0,0,0,1,a[i].c,a[i].c},srt[i]=cnt; if(!a[i].fa) RT=i; else add(a[i].fa,i); }dfs(RT); printf("%lld\n",ans); return 0; }

D - Sequence (Day1)

应该说是最有价值的一题了.
首先先做一个经典tricktricktrick，将每个aia_iai−i-i−i，从而将严格单调变成不降.
然后，考虑特殊情形，例如单减，显然要全取中位数.
那么我们将所有极大单减分量先组起来，再去考虑如何将几个分量糅合从而满足题目的不降条件.
画图易证:::如果不满足条件，那么直接往前糅合一定最优.
具体实现考虑用栈，每次加入就将他不断向前糅合，糅合用左偏树实现.

#include<bits/stdc++.h> # define Maxn 1000005 # define ll long long using namespace std; int n,a[Maxn],b[Maxn],tot; int s[Maxn],top,id[Maxn],All[Maxn]; ll ans; struct Node{int fa,l,r,dist,sz,v;}tr[Maxn]; int Merge(int x,int y) { if((!x)||(!y)) return x+y; if(tr[x].v<tr[y].v) swap(x,y); tr[x].r=Merge(tr[x].r,y); if(tr[tr[x].l].dist<tr[tr[x].r].dist) swap(tr[x].l,tr[x].r); tr[x].dist=tr[tr[x].r].dist+1; tr[x].sz=tr[tr[x].l].sz+tr[tr[x].r].sz+1; return x; } int Del(int x) { int rt=tr[x].fa=tr[tr[x].l].fa=tr[tr[x].r].fa=Merge(tr[x].l,tr[x].r); return rt; } int L[Maxn],R[Maxn]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]),a[i]-=i; tr[++tot]={tot,0,0,0,1,a[i]}; int now=tot,sum=1,sl=i; while(top&&tr[s[top]].v>tr[now].v) { now=tr[now].fa=tr[s[top]].fa=Merge(now,s[top]); sum+=All[top--]; while(tr[now].sz>(sum+1)/2) now=Del(now); }s[++top]=now,All[top]=sum; } int k=1; for(int i=1;i<=top;i++) { for(int j=1;j<=All[i];j++) { b[k++]=tr[s[i]].v; ans+=abs(a[k-1]-b[k-1]); } } printf("%lld\n",ans); for(int i=1;i<=n;i++) printf("%d\n",b[i]+i); return 0; }

E - 城池攻占

维护每个城池上的骑士，然后就没了.

#include<bits/stdc++.h> # define Maxn 300005 # define ll long long using namespace std; int n,m,srt[Maxn],cnt; int head[Maxn],tot=1; struct Edge{int to,next;}e[Maxn]; struct Node{int fa,a;ll h,v;}a[Maxn]; struct Tree{int fa,l,r,dist,sz,id;ll v,lz1=1,lz2=0;}tr[Maxn<<1]; void add(int u,int v) { e[tot]={v,head[u]}; head[u]=tot++; } int s[Maxn],c[Maxn],dep[Maxn],sum1[Maxn],sum2[Maxn]; void Put(int rt,ll v1,ll v2) { tr[rt].v=tr[rt].v*v1+v2; tr[rt].lz1*=v1,tr[rt].lz2*=v1,tr[rt].lz2+=v2; } void Push(int rt) { Put(tr[rt].l,tr[rt].lz1,tr[rt].lz2); Put(tr[rt].r,tr[rt].lz1,tr[rt].lz2); tr[rt].lz1=1,tr[rt].lz2=0; } int Merge(int x,int y) { Push(x),Push(y); if((!x)||(!y)) return x+y; if(tr[x].v>tr[y].v) swap(x,y); tr[x].r=Merge(tr[x].r,y); if(tr[tr[x].l].dist<tr[tr[x].r].dist) swap(tr[x].l,tr[x].r); tr[x].dist=tr[tr[x].r].dist+1; tr[x].sz=tr[tr[x].l].sz+tr[tr[x].r].sz+1; return x; } int Del(int x) { int rt=tr[x].fa=tr[tr[x].l].fa=tr[tr[x].r].fa=Merge(tr[x].l,tr[x].r); return rt; } void dfs(int rt) { for(int i=head[rt];i;i=e[i].next) { dep[e[i].to]=dep[rt]+1,dfs(e[i].to); srt[rt]=tr[srt[rt]].fa=tr[srt[e[i].to]].fa=Merge(srt[rt],srt[e[i].to]); } while(tr[srt[rt]].sz&&tr[srt[rt]].v<a[rt].h) { sum1[rt]++,sum2[tr[srt[rt]].id]=dep[c[tr[srt[rt]].id]]-dep[rt]; srt[rt]=Del(srt[rt]); } if(a[rt].a==0) Put(srt[rt],1,a[rt].v); else Put(srt[rt],a[rt].v,0); } int main() { scanf("%d%d",&n,&m),cnt=n; for(int i=1;i<=n;i++) scanf("%lld",&a[i].h); for(int i=2;i<=n;i++) { scanf("%d%d%lld",&a[i].fa,&a[i].a,&a[i].v); add(a[i].fa,i); } for(int i=1;i<=m;i++) { scanf("%d%d",&s[i],&c[i]),cnt++; tr[cnt].fa=tr[cnt].l=tr[cnt].r=tr[cnt].dist=0,tr[cnt].sz=1,tr[cnt].id=i,tr[cnt].v=s[i]; srt[c[i]]=tr[srt[c[i]]].fa=tr[cnt].fa=Merge(srt[c[i]],cnt); }dfs(1); while(tr[srt[1]].sz) { sum2[tr[srt[1]].id]=dep[c[tr[srt[1]].id]]+1; srt[1]=Del(srt[1]); } for(int i=1;i<=n;i++) printf("%d\n",sum1[i]); for(int i=1;i<=m;i++) printf("%d\n",sum2[i]); return 0; }