可并堆（实际上只有左倾树）
HJWJBSR
posted @ 2015年5月31日 18:52
in 专题
, 358 阅读
最近状态实在爆炸，不知为何做题真心没劲。
学了下左倾树，（二项堆到现在都没写，因为没看到有什么题是二项堆能写但是左倾树不能的= =）然后做了两道裸题：
BZOJ2333棘手的操作：= =2333。。本来想怎么用二项堆做的= =但是二项堆貌似打标记很困难的样子，然后果断写了左倾树。然后这些操作就裸了。。（第一次写的左倾树代码好丑，还是不要看的好 虽然我的代码一直很丑。。。）
#include <iostream>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define N 500050
#define INF 0x7f7f7f7f
struct Point
{
int c[2],fa,v,adv,h,sg;bool ad;
} a[N];
int n,m,add=0,t[N];
multiset <int> li;
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline void adj (int x)
{
if (!x||!a[x].ad) return;
a[x].v+=a[x].adv;
a[a[x].c[0]].ad=a[a[x].c[1]].ad=1;
a[a[x].c[0]].adv+=a[x].adv;a[a[x].c[1]].adv+=a[x].adv;
a[0].ad=a[0].adv=a[x].ad=a[x].adv=0;
return;
}
inline void Down(int x)
{
adj(x);adj(a[x].c[0]);adj(a[x].c[1]);
return;
}
void DFS (int x)
{
if (a[x].fa) DFS(a[x].fa);Down(x);
return;
}
int Merge(int x,int y)
{
if (!x||!y) return x+y;
Down(x);Down(y);
if (a[y].v>a[x].v)
swap(x,y);
a[x].c[1]=Merge(a[x].c[1],y);a[a[x].c[1]].fa=x;
a[x].h=min(a[a[x].c[1]].h,a[a[x].c[0]].h)+1;
if (a[x].h!=a[a[x].c[1]].h+1)
swap(a[x].c[0],a[x].c[1]);
return x;
}
inline void Line (int x,int y)
{
while (a[x].fa) x=a[x].fa;
while (a[y].fa) y=a[y].fa;
if (x==y) return;
li.erase(li.lower_bound(-a[x].v));
li.erase(li.lower_bound(-a[y].v));
li.insert(-a[Merge(x,y)].v);
return;
}
int main()
{
int i,j,k,l,q,w,e;
set <int> :: iterator it;
char b[20];li.clear();
scanf("%d",&n);a[0].v=INF;a[0].h=0;
for (i=1;i<=n;i++)
a[i].v=Read(),a[i].c[0]=a[i].c[1]=a[i].ad=a[i].adv=
a[i].fa=a[i].ad=0,a[i].h=1,li.insert(-a[i].v),
t[i]=a[i].sg=i;
scanf("%d",&m);
for (i=1;i<=m;i++)
{
scanf("%s",b);
if (b[0]=='F')
{
if (b[1]=='1')
DFS(k=t[Read()]),printf("%d\n",a[k].v+add);else
if (b[1]=='2')
{
k=Read();
while (a[k].fa) k=a[k].fa;
printf("%d\n",a[k].v+add);
}else printf("%d\n",-*li.begin()+add);
}else
if (b[0]=='A')
{
if (b[1]=='3') add+=Read();else
if (b[1]=='2')
{
k=Read();
while (a[k].fa) k=a[k].fa;
a[k].ad=1;a[k].adv=Read();
li.erase(li.lower_bound(-a[k].v));
Down(k);
li.insert(-a[k].v);
}else
{
DFS(k=t[Read()]);l=Read();
if (l<0)
{
w=a[k].fa;
if (!w) li.erase(li.lower_bound(-a[k].v));
a[k].v+=l;
while (1)
{
Down(k);
q=a[k].c[!a[k].c[0]||(a[k].c[1]&&a[k].
c[0]&&a[a[k].c[1]].v>a[a[k].c[0]].v)];
if (q&&a[q].v>a[k].v)
swap(a[q].v,a[k].v),
swap(a[q].sg,a[k].sg),
swap(t[a[q].sg],t[a[k].sg]),k=q;else
break;
}
if (!w)
{
while (a[k].fa) k=a[k].fa;
li.insert(-a[k].v);
}
}else
if (!a[k].fa)
{
li.erase(li.lower_bound(-a[k].v));
a[k].v+=l;li.insert(-a[k].v);
}else
{
a[k].v+=l;
while (a[k].v>a[a[k].fa].v&&a[a[k].fa].fa)
swap(a[k].v,a[a[k].fa].v),
swap(a[k].sg,a[a[k].fa].sg),
swap(t[a[k].sg],t[a[a[k].fa].sg]),
k=a[k].fa;
if (a[k].v>a[a[k].fa].v)
li.erase(li.lower_bound(-a[a[k].fa].v)),
li.insert(-a[k].v),
swap(a[k].v,a[a[k].fa].v),
swap(a[k].sg,a[a[k].fa].sg),
swap(t[a[k].sg],t[a[a[k].fa].sg]);
}
}
}else
Line(Read(),Read());
}
return 0;
}
BZOJ2809dispatching：据说是P神那届APIO的题，感觉还是很裸，我写了左倾树启发式合并。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
#define INF 0x7f7f7f7f
#define ll long long
ll ans=0,t[N];
int n,m,v[N],fa[N],c[N][2],fi[N],ne[N],gf[N],h[N],sum[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline int Merge(int x,int y)
{
if (!x||!y) return x+y;
if (v[x]<v[y]) swap(x,y);
c[x][1]=Merge(c[x][1],y);fa[c[x][1]]=x;
h[x]=min(h[c[x][0]],h[c[x][1]])+1;
if (h[x]!=h[c[x][1]]+1)
swap(c[x][1],c[x][0]);
return x;
}
inline int Pop(int x)
{
int i=v[gf[x]];
gf[x]=Merge(c[gf[x]][0],c[gf[x]][1]);fa[gf[x]]=0;
return i;
}
int DFS(int x)
{
int i,j,k,l,q,w,e;ll s=0;
gf[x]=x;h[x]=1;s=v[x];sum[x]=1;
for (i=fi[x];i;i=ne[i])
{
s+=DFS(i);gf[x]=Merge(gf[i],gf[x]);sum[x]+=sum[i];
}
while (s>m) s-=Pop(x),sum[x]--;
ans=max(t[x]*sum[x],ans);
return s;
}
int main()
{
int i,j,k,l,q,w,e;
memset(v,0,sizeof(v));memset(t,0,sizeof(t));
memset(c,0,sizeof(c));memset(h,0,sizeof(h));
memset(fi,0,sizeof(fi));memset(ne,0,sizeof(ne));
memset(gf,0,sizeof(gf));memset(fa,0,sizeof(fa));
memset(sum,0,sizeof(sum));
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
fa[i]=Read(),v[i]=Read(),t[i]=Read(),
ne[i]=fi[fa[i]],fi[fa[i]]=i;
DFS(1);
printf("%lld\n",ans);
return 0;
}
还有道题跟可并堆并没有什么关系的：
BZOJ1078斜堆：思路也都想的差不多，但是感觉自己就是集中不了注意力，感觉一直在胡思乱想，然后就直接翻题解去了，这种状态还怎么愉快地玩耍啊！其实感觉好像是晚饭吃太饱了= =可以发现最后删除的结点一定在当前树一直往左的路径上，并且不会有右子树，并且一定是这些点中深度最小的（还有种情况是左路径上存在两个没有右子树的点互为父子则选叶子结点的那个），这些性质都十分可证。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 205
#define INF 0x7f7f7f7f
int fa[N],gf=0,c[N][2],n,m,li[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int DFS(int x)
{
int i;
if (!c[x][1]&&(!c[x][0]||c[c[x][0]][0]+c[c[x][0]][1]))
{
if (fa[x])
c[fa[x]][0]=c[x][0];else
gf=c[x][0];
fa[c[x][0]]=fa[x];
return x;
}
i=DFS(c[x][0]);swap(c[x][0],c[x][1]);
return i;
}
int main()
{
int i,j,k,l,q,w,e;
memset(fa,0,sizeof(fa));memset(c,0,sizeof(c));
scanf("%d",&n);gf=n+1;
for (i=1;i<=n;i++)
{
k=Read();
if (k<100) c[k][0]=i;else c[k-=100][1]=i;
fa[i]=k;
}
c[n+1][0]=c[0][0];c[n+1][1]=c[0][1];
fa[c[n+1][0]]=n+1;fa[c[n+1][1]]=n+1;
c[0][0]=c[0][1]=0;
for (i=1;i<=n+1;i++)
li[n+1-i]=DFS(gf);
for (i=0;i<=n;i++)
printf("%d ",li[i]==n+1?0:li[i]);
printf("\n");
return 0;
}
BZOJ4003城池攻占：裸的打标记左倾树，一开始写丑了，加了一堆不必要的东西，然后不想重写，于是一直改一直wa，后来重写之后又wa了几次终于过了。代码能力是硬伤！
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 300050
#define INF 0x7f7f7f7f
#define ll long long
int s[N],ss[N],gf[N],n,m,as[N],h[N];
int c[N][2],fi[N],ne[N],ff[N],nf[N],a[N];
ll v[N],t[N],ad[N],xj[N],r[N];
inline ll Read()
{
ll x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline void Down(int x)
{
if (!x) return;
if (xj[x]!=1)
{
t[x]*=xj[x];ad[c[x][0]]*=xj[x];ad[c[x][1]]*=xj[x];
xj[c[x][0]]*=xj[x];xj[c[x][1]]*=xj[x];xj[x]=1;
}
if (ad[x])
{
t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x];ad[x]=0;
}
if (as[x])
{
s[x]+=as[x];as[c[x][0]]+=as[x];as[c[x][1]]+=as[x];as[x]=0;
}
return;
}
int Merge(int x,int y)
{
if (!x||!y) return x+y;
Down(x);Down(y);
if (t[x]>t[y]) swap(x,y);
c[x][1]=Merge(c[x][1],y);
h[x]=min(h[c[x][1]],h[c[x][0]])+1;
if (h[x]!=h[c[x][1]]+1) swap(c[x][0],c[x][1]);
return x;
}
inline void Pop(int x)
{
ss[x]++;gf[x]=Merge(c[gf[x]][0],c[gf[x]][1]);
return;
}
void DFS(int x)
{
for (int i=ff[x];i;i=nf[i])
gf[x]=Merge(gf[x],i);
for (int i=fi[x];i;i=ne[i])
DFS(i),gf[x]=Merge(gf[x],gf[i]);
while (Down(gf[x]),t[gf[x]]<v[x]&&gf[x]) Pop(x);
if (!gf[x]) return;Down(gf[x]);
if (a[x]) xj[gf[x]]=r[x];else ad[gf[x]]=r[x];
as[gf[x]]=1;
return;
}
int main()
{
int i,j,k,l,q,w,e;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) v[i]=Read();
for (i=2;i<=n;i++)
ne[i]=fi[k=Read()],fi[k]=i,a[i]=Read(),r[i]=Read();
for (i=1;i<=m;i++)
t[i]=Read(),nf[i]=ff[k=Read()],ff[k]=i,xj[i]=h[i]=1;
v[0]=(ll)(1e18);
fi[0]=1;DFS(0);
for (i=1;i<=n;i++)
printf("%d\n",ss[i]);
for (i=1;i<=m;i++)
printf("%d\n",s[i]);
return 0;
}
可并堆也更到这里算了，话说右边那个播放器感觉蛮好玩的于是搞了一个，把看过的一些番的不错的OP、ED、人物歌什么的放上来了，Claris赛高！
评论 (0)
