题解 P3224 【[HNOI2012]永无乡】

· · 题解

P3224永无乡

主体思路：权值线段树+线段树合并（无指针）太蒻不会指针QAQ

代码效率：859ms 即使用了O2和常数优化，还是差不多是最劣解的程度，所以请谨慎参考QAQ

忽然发现：这里还没有无指针权值线段树的写法嗷！于是我就来啦QWQ

虽然比平衡树要慢，但是比平衡树好学多啦QWQ

题目中要求我们支持查询第k小值，所以容易想到权值线段树

然后又有合并操作，容易想到线段树合并

然后我们发现做的时候需要维护一下连通性，容易想到并查集

嗯，然后我们就能通过本题了！

还有几点要注意的地方：

比如说并查集是f[b]=a,那么合并线段树也需要b向a合并的样子。

嗯，没啦！来看代码QWQ

如果有帮到你，记得点赞哦qwq

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=100010;
const int M=3200010;
int n,m,q,cnt,rt[N],f[N];
int ls[M],rs[M],id[M],sum[M];
char ch[5];
inline int read(){
    int x=0,w=1;
    char ch;ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*w;
}
inline int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
inline void update(int a){sum[a]=sum[ls[a]]+sum[rs[a]];}
inline int add(int a,int x,int y,int pos,int idx){
    if(!a) a=++cnt;
    if(x==y) {id[a]=idx;sum[a]++;return a;}
    int mid=(x+y)>>1;
    if(pos<=mid) ls[a]=add(ls[a],x,mid,pos,idx);
    else rs[a]=add(rs[a],mid+1,y,pos,idx);
    update(a);
    return a;
}
inline int merge(int a,int b,int x,int y){
    if(!a) return b;
    if(!b) return a;
    if(x==y) {if(id[b]) {id[a]=id[b];sum[a]+=sum[b];}return a;}
    int mid=(x+y)>>1;
    ls[a]=merge(ls[a],ls[b],x,mid);
    rs[a]=merge(rs[a],rs[b],mid+1,y);
    update(a);
    return a;
}
inline int query(int a,int k,int x,int y){
    int ans;
    if(sum[a]<k||!a) return 0;
    if(x==y) return id[a];
    int mid=(x+y)>>1;
    if(k<=sum[ls[a]]) ans=query(ls[a],k,x,mid);
    else ans=query(rs[a],k-sum[ls[a]],mid+1,y);
    return ans;
}
int main()
{
    int x,y;
    n=read();m=read();
    for(register int i=1;i<=n;i++){
        f[i]=i;
        x=read();
        rt[i]=add(rt[i],1,n,x,i);
    }
    for(register int i=1;i<=m;i++){
        x=read();y=read();
        x=getf(x);y=getf(y);
        f[y]=x;
        rt[x]=merge(rt[x],rt[y],1,n);
    }
    q=read();
    while(q--){
        scanf("%s",ch);
        if(ch[0]=='B'){
            x=read();y=read();
            x=getf(x);y=getf(y);
            if(x==y) continue;
            f[y]=x;
            rt[x]=merge(rt[x],rt[y],1,n);
        }
        else{
            x=read();y=read();
            x=getf(x);
            int ans=query(rt[x],y,1,n);
            if(!ans) printf("-1\n");
            else printf("%d\n",ans);
        }
    }
    return 0;
}

后记：

我是今天才发现自己不会权值线段树的，这个写法也是自己摸索出来的，如果有写的不准确的地方，请大佬多多指正啦QAQ