Loading...

洛谷P3224 [HNOI2012]永无乡

check评论:0 条 remove_red_eye浏览量:74 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-11-05

原题链接

  • 题目描述
给定n个点,他们的权值是1-n的一种排列,两种操作,连接两个点以及查询某一个点所在连通块第k小权值
  • 题目分析

连接两个点,不想写$LCT$,那显然就是线段树合并(大雾

显然第$k$小是全局范围下讨论的,权值线段树合并查询答案即可

  • 代码实现
#include <bits/stdc++.h>
using namespace std;
int rt[100010],val[100010],f[100010],bh[100010],sum[4000010],ls[4000010],rs[4000010];
int n,m,cnt,to[100010];
int find(int x)
{
    if(x==f[x])
    {
        return x;
    }
    return f[x]=find(f[x]);
}
void ins(int &o,int lf,int rg,int w)
{
    if(!o)
    {
        o=++cnt;
    }
    sum[o]++;
    if(lf==rg)
    {
        return ;
    }
    int mid=(lf+rg)>>1;
    if(w<=mid)
    {
        ins(ls[o],lf,mid,w);
    }
    if(mid<w)
    {
        ins(rs[o],mid+1,rg,w);
    }
    return ;
}
int merge(int x,int y)
{
    if(!x)
    {
        return y;
    }
    if(!y)
    {
        return x;
    }
    int t=++cnt;
    sum[t]=sum[x]+sum[y];
    ls[t]=merge(ls[x],ls[y]);
    rs[t]=merge(rs[x],rs[y]);
    return t;
}
int query(int o,int lf,int rg,int k)
{
    if(lf==rg)
    {
        return lf;
    }
    int mid=(lf+rg)>>1;
    if(sum[ls[o]]>=k)
    {
        return query(ls[o],lf,mid,k);
    }
    else
    {
        return query(rs[o],mid+1,rg,k-sum[ls[o]]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        ins(rt[i],1,n,val[i]);
        to[val[i]]=i;
        f[i]=i;
    }   
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int dx=find(x),dy=find(y);
        if(dx!=dy)
        {
            f[dx]=dy;
            rt[dy]=merge(rt[dy],rt[dx]);
        }
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        char opt[4];
        int x,y;
        scanf("%s%d%d",opt,&x,&y);
        if(opt[0]=='Q')
        {
            int dx=find(x);
            if(sum[rt[dx]]<y)
            {
                cout<<-1<<"\n";
                continue;
            }
            printf("%d\n",to[query(rt[dx],1,n,y)]);
        }
        else
        {
            int dx=find(x),dy=find(y);
            if(dx!=dy)
            {
                f[dx]=dy;
                rt[dy]=merge(rt[dy],rt[dx]);
            }
        }
    }
} 

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名