admin 管理员组

文章数量: 1087649

洛谷P3224【HNOI2012】永无乡

洛谷P3224【HNOI2012】永无乡

题目大意

有 n n n个点，每个点都有一个重要度。先连接 m m m条边，然后有 q q q次操作：

B x y 表示连接点 x x x和点 y y y

Q x k 表示询问当前与点 x x x 连通的所有点中第 k k k 重要的是哪个点

题解

这道题需要用到并查集和线段树合并。

开始时对每一座岛建立一棵线段树，第 i i i个叶节点为一表示重要程度为 i i i的岛与这个岛连通。维护区间叶节点数量 s s s， r t [ i ] rt[i] rt[i]表示节点 i i i的权值线段树的根，然后对 M M M条边进行合并。比如对于边 ( a , b ) (a,b) (a,b)，如果 a , b a,b a,b不在一个连通块，则设 x = f i n d ( a ) , y = f i n d ( b ) x=find(a),y=find(b) x=find(a),y=find(b)，将 x x x的线段树和 y y y的线段树进行合并，然后 f a [ y ] = x fa[y]=x fa[y]=x，表示将 y y y的线段树合并到 x x x的线段树中。

对于 B B B操作，同上，并查集处理即可。对于 Q Q Q操作，查找 x x x的线段树，找到第 k k k小的叶节点即可。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,q,tot=0,x,y,c[100005],re[100005],rt[100005],fa[100005],s[5000005];
char ch;
struct node{int lc,rc;
}tr[5000005];
int find(int ff){if(fa[ff]!=ff) fa[ff]=find(fa[ff]);return fa[ff];
}
void pt(int &k,int l,int r,int v){if(!k) k=++tot;if(l==r&&l==v){++s[k];return;}if(l>v||r<v) return;if(l==r) return;int mid=(l+r)/2;if(v<=mid) pt(tr[k].lc,l,mid,v);else pt(tr[k].rc,mid+1,r,v);s[k]=s[tr[k].lc]+s[tr[k].rc];
}
void merge(int &r1,int r2,int l,int r){if(!r1||!r2){r1=r1+r2;return;}if(l==r){s[r1]+=s[r2];return;}int mid=(l+r)/2;merge(tr[r1].lc,tr[r2].lc,l,mid);merge(tr[r1].rc,tr[r2].rc,mid+1,r);s[r1]=s[tr[r1].lc]+s[tr[r1].rc];
}
void gt(int x,int y){int x1=find(x),x2=find(y);if(x1==x2) return;merge(rt[x1],rt[x2],1,n);fa[x2]=x1;
}
int find(int k,int l,int r,int v){if(!k) return -1;if(l==r){if(v==1) return re[l];return -1;}int mid=(l+r)/2;if(v<=s[tr[k].lc]&&tr[k].lc) return find(tr[k].lc,l,mid,v);return find(tr[k].rc,mid+1,r,v-s[tr[k].lc]);
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&c[i]);re[c[i]]=i;fa[i]=i;pt(rt[i],1,n,c[i]);}for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);gt(x,y);}scanf("%d",&q);while(q--){ch=getchar();while(ch!='B'&&ch!='Q') ch=getchar();scanf("%d%d",&x,&y);if(ch=='B'){gt(x,y);}else{x=find(x);printf("%d\n",find(rt[x],1,n,y));}}return 0;
}

本文标签： 洛谷P3224HNOI2012永无乡

版权声明：本文标题：洛谷P3224【HNOI2012】永无乡 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1687330535a90328.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。