[HNOI2012]永无乡
题意:
一共 \(n\) 个点,每个点权值,给你 \(q\) 个操作:
-
B x y
表示连接 \(x,y\) -
Q x k
表示求当前 \(x\) 所在连通块内权值第 \(k\) 小的点的编号
分析:
求一个联通块内的权值第 \(k\) 小的点,很容易想到主席树或者权值线段树,但是考虑到有合并连通块的操作,因此可以确定写法:
权值线段树+线段树合并
代码:
考虑记录信息:正常的权值线段树只用记录数的个数,但是我们还要输出编号,因此用一个 \(id\) 数组记录这个点对应的编号。
首先,先建立权值线段树:
int add(int x,int l,int r,int pos,int c){
if(!x) x=++cnt;
if(l==r){
t[x].id=c; t[x].sum++; return x;
}
int mid=l+r>>1;
if(pos<=mid) t[x].ls=add(t[x].ls,l,mid,pos,c);
else t[x].rs=add(t[x].rs,mid+1,r,pos,c);
push_up(x);
return x;
}
.....
for(int i=1,x;i<=n;i++){
fa[i]=i; scanf("%d",&x); rt[i]=add(rt[i],1,n,x,i);
}
不像正常的直接建立的权值线段树,我们需要记录这个节点所对应的编号,这样合并时才不会出问题。
然后,对于每一个建边操作,我们都进行一次线段树合并:
找到 \(x\) ,\(y\) 所在连通块的根 \(fx,fy\) ,合并这两个根代表的编号的连通块,即是符合要求的合并
询问建边和预建边的操作是一样的。当然,两者在同一个连通块内就不用管了
int merge(int p,int q,int l,int r){//合并线段树要和合并树状数组方向一致
if(!p) return q;
if(!q) return p;
if(l==r){
t[p].id=t[q].id; t[p].sum+=t[q].sum;
return p;
}
int mid=l+r>>1;
t[p].ls=merge(t[p].ls,t[q].ls,l,mid);
t[p].rs=merge(t[p].rs,t[q].rs,mid+1,r);
push_up(p);
return p;
}
····
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y); x=get(x),y=get(y);
fa[y]=x;
rt[x]=merge(rt[x],rt[y],1,n);
}
查询时,就是正常的查询 \(x\) 的根节点的权值线段树的第 \(k\) 小值,这是权值线段树的基本操作。
int query(int x,int l,int r,int k){
if(t[x].sum<k||!x) return 0;//没这么多数或者没这个点
if(l==r) return t[x].id;
int mid=l+r>>1,ans;
if(k<=t[t[x].ls].sum) ans=query(t[x].ls,l,mid,k);
else ans=query(t[x].rs,mid+1,r,k-t[t[x].ls].sum);
return ans;
}
·····
else{
scanf("%d%d",&x,&y); x=get(x);
int ans=query(rt[x],1,n,y);
if(!ans) puts("-1");
else cout<<ans<<endl;
}
整体代码在这里:My Luogu