洛谷P3224 [HNOI2012]永无乡线段树合并

心已赠人 2023-06-04 07:58 20阅读 0赞

[**题面**][Link 1]

**题解：**

**线段树合并的好题。在这题中我们可以用并查集维护连通块，因为要统计第k大，所以还可以用线段树合并来统计子树之间的信息。**

**坑点：1：注意炸内存 2：最后输出的是编号，要存起来 3：注意值域线段树中查询第k大的写法**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    using namespace std;
    const int N=5000005;
    int root[N];
    int n,m;
    int T;
    int lc[N],rc[N];
    int sum[N];
    int fa[N];
    int rev[N];
    int maxx;
    int x,y;
    int o1,o2;
    int k;
    int kkk;
    int val;
    char opt[2];
    int ans;
    int get(int x){
         //并查集维护连通块 
        if(x!=fa[x]) return fa[x]=get(fa[x]);
    }
    void build(int &rt,int l,int r,int v){
        if(!rt) rt=++T;
        if(l==r){
            sum[rt]++;
            return;
        } 
        int mid=(l+r)>>1;
        if(v<=mid) build(lc[rt],l,mid,v);
        else build(rc[rt],mid+1,r,v);
        sum[rt]=sum[lc[rt]]+sum[rc[rt]];
    }
    int merge(int x,int y){
        if(!x||!y)    return x+y;
        int now=++T;
        sum[now]=sum[x]+sum[y];
        lc[now]=merge(lc[x],lc[y]);
        rc[now]=merge(rc[x],rc[y]);
        return now;
    }
    int query(int rt,int l,int r,int k){
         //查询第k大 
        if(sum[rt]<k) return 0;
        if(l==r) return l;
        int mid=(l+r)>>1;
        if(sum[lc[rt]]>=k) return query(lc[rt],l,mid,k);
        else return query(rc[rt],mid+1,r,k-sum[lc[rt]]);  
    }
    void united(int x,int y){
         //合并，并查集和线段树一起合并 
        int f1=get(x);
        int f2=get(y);
        if(f1!=f2) fa[f1]=f2;
        root[f2]=merge(root[f1],root[f2]);
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=n;i++){
            scanf("%d",&val);
            rev[val]=i;
            build(root[i],1,n,val);
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            united(x,y); 
        } 
        scanf("%d",&k);
        while(k--){
            scanf("%s",opt);
            if(opt[0]=='B'){
                scanf("%d%d",&o1,&o2);
                united(o1,o2);    
            }
            else{
                scanf("%d%d",&o1,&kkk); 
                int ljb=root[get(o1)];
                if(sum[ljb]<kkk) printf("-1\n");
                else printf("%d\n",rev[query(ljb,1,n,kkk)]);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11236045.html

[Link 1]: https://www.luogu.org/problemnew/show/P3224
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/badb3324a0e74e8f931722460e50a11d.png