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;
}

后记

后来发现这道题还有更优的平衡树解法，但这个做法应该是码量最少的了，这也说明了值域线段树可以实现一些普通平衡树的操作，但不能完全替代。