P3224 [HNOI2012]永无乡 题解
题意概括
有若干集合,每个集合最初包含一个值,和一个编号1~n。两个操作:合并两个集合,查询包含值x的集合中第k大值最初的集合编号。
思路
维护集合之间关系显然用并查集,但怎么处理询问,如果只是问最大值,那么显然可以用线段树把最大值存在并查集的祖先上,当然线段树也行。但这里问的是第k大。主席树?主席树是用来处理区间第k大的,而这里每棵树显然储存一整个集合(由多个小集合合并来的)的信息,我们并不关心这个集合内的区间问题,主席树便有点大材小用。所以,得出结论:用并查集和值域(权值)线段树合并。
你的线段树本来就能合并,那并查集是干嘛的呢?我们每次合并是取出x集合和y集合对应的A树和B树,并将B树的信息放到A上,就像这样:A B=>A+B B 如果是 A B=>A+B A+B或A B C(=A+B) 空间势必会炸。若不用并查集我们在查询集合y时,可能拿到的rt[y]树y的根就可能是 A B=>A+B B 中的那个B的而不是A+B的。用了并查集先把 f[y]=x 这样 rt[f[y] 就是 A+B 的根了。(不知不觉写了好多)
实现
其实实现很简单,但对于不熟悉值域线段树和线段树合并的人就不容易了。
值域线段树
先放这道题里涉及值域线段树的代码(代码总是比人话好理解):
int newt(int l,int r,int val)//建一棵只有一个值的树
{
int now=++tot;
t[now].v=1;
if(l==r)
return now;
int mid=l+r>>1;
if(mid>=val)
t[now].l=newt(l,mid,val);
else
t[now].r=newt(mid+1,r,val);
pushup(now);
return now;
}
int query(int now,int l,int r,int val)//查询
{
if(t[now].v<val||!now)return 0;
if(l==r)
return l;
int mid=(l+r)>>1;
if(val<=t[t[now].l].v)
return query(t[now].l,l,mid,val);
else
return query(t[now].r,mid+1,r,val-t[t[now].l].v);
}
详细请看这位大佬的blog。
线段树合并
int merge(int x,int y,int l,int r)
{
if(!x||!y)return x+y;
if(l==r){t[x].v=t[x].v+t[y].v;return x;}
int mid=l+r>>1;
t[x].l=merge(t[x].l,t[y].l,l,mid);
t[x].r=merge(t[x].r,t[y].r,mid+1,r);
pushup(x);
return x;
}
请看这位蒟蒻(我)的blog。
AC代码
#include<bits/stdc++.h>
using namespace std;
struct TREE
{
int v,l,r;
}t[5000005];
int n,m,p[100005],f[100005],rt[100005],id[100005],q,x,y,u,v,tot,k;
char op;
void pushup(int now)
{
t[now].v=t[t[now].l].v+t[t[now].r].v;
}
int find(int now)
{
if(f[now]==now)return now;
else return f[now]=find(f[now]);
}
int newt(int l,int r,int val)
{
//cout<<l<<' '<<r<<' '<<val<<endl;
int now=++tot;
t[now].v=1;
if(l==r)
return now;
int mid=l+r>>1;
if(mid>=val)
t[now].l=newt(l,mid,val);
else
t[now].r=newt(mid+1,r,val);
pushup(now);
return now;
}
int merge(int x,int y,int l,int r)
{
//cout<<x<<' '<<y<<' '<<l<<' '<<r<<endl;
if(!x||!y)return x+y;
if(l==r){t[x].v=t[x].v+t[y].v;return x;}
int mid=l+r>>1;
t[x].l=merge(t[x].l,t[y].l,l,mid);
t[x].r=merge(t[x].r,t[y].r,mid+1,r);
pushup(x);
return x;
}
int query(int now,int l,int r,int val)
{
//cout<<now<<' '<<l<<' '<<r<<endl;
if(t[now].v<val||!now)return 0;
if(l==r)
return l;
int mid=(l+r)>>1;
if(val<=t[t[now].l].v)
return query(t[now].l,l,mid,val);
else
return query(t[now].r,mid+1,r,val-t[t[now].l].v);
}
void pp()
{
for(int i=1;i<=tot;i++)cout<<setw(2)<<i<<' ';cout<<endl;
for(int i=1;i<=tot;i++)cout<<setw(2)<<f[i]<<' ';cout<<endl;
for(int i=1;i<=tot;i++)cout<<setw(2)<<rt[i]<<' ';cout<<endl;
cout<<endl;
for(int i=1;i<=tot;i++)cout<<setw(2)<<t[i].v<<' ';cout<<endl;
for(int i=1;i<=tot;i++)cout<<setw(2)<<t[i].l<<' ';cout<<endl;
for(int i=1;i<=tot;i++)cout<<setw(2)<<t[i].r<<' ';cout<<endl;
cout<<endl;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>p[i],rt[i]=newt(1,n,p[i]),f[i]=i,id[p[i]]=i;
id[0]=-1;
//pp();
for(int i=1;i<=m;i++)
{
cin>>u>>v;
if(find(u)==find(v))continue;
rt[find(u)]=merge(rt[find(u)],rt[find(v)],1,n);
f[find(v)]=find(u);
}
cin>>q;
while(q--)
{
//
cin>>op;
if(op=='Q')
{
cin>>x>>y;
cout<<id[query(rt[find(x)],1,n,y)]<<endl;
}
if(op=='B')
{
cin>>u>>v;
if(find(u)!=find(v))
rt[find(u)]=merge(rt[find(u)],rt[find(v)],1,n),f[find(v)]=find(u);
}
}
return 0;
}
后记
后来发现这道题还有更优的平衡树解法,但这个做法应该是码量最少的了,这也说明了值域线段树可以实现一些普通平衡树的操作,但不能完全替代。