永无乡

题目描述

永无乡包含 nn 座岛，编号从 11 到 nn ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 nn 座岛排名，名次用 11 到 nn 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 aa 出发经过若干座（含 00 座）桥可以 到达岛 bb ，则称岛 aa 和岛 bb 是连通的。

现在有两种操作：

B x y 表示在岛 xx 与岛 yy 之间修建一座新桥。

Q x k 表示询问当前与岛 xx 连通的所有岛中第 kk 重要的是哪座岛，即所有与岛 xx 连通的岛中重要度排名第 kk 小的岛是哪座，请你输出那个岛的编号。

输入输出格式

输入格式：

第一行是用空格隔开的两个正整数 nn 和 mm ，分别表示岛的个数以及一开始存在的桥数。

接下来的一行是用空格隔开的 nn 个数，依次描述从岛 11 到岛 nn 的重要度排名。随后的 mm 行每行是用空格隔开的两个正整数 a_iai​ 和 b_ibi​ ，表示一开始就存在一座连接岛 a_iai​ 和岛 b_ibi​ 的桥。

后面剩下的部分描述操作，该部分的第一行是一个正整数 qq ，表示一共有 qq 个操作，接下来的 qq 行依次描述每个操作，操作的 格式如上所述，以大写字母 QQ 或 BB 开始，后面跟两个不超过 nn 的正整数，字母与数字以及两个数字之间用空格隔开。

输出格式：

对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出 -1−1 。

输入输出样例

输入样例#1：

5 1

4 3 2 5 1

1 2

7

Q 3 2

Q 2 1

B 2 3

B 1 5

Q 2 1

Q 2 4

Q 2 3

输出样例#1：

-1

2

5

1

2

说明

对于 20% 的数据 \(n \leq 1000, q \leq 1000\)

对于 100% 的数据 \(n \leq 100000, m \leq n, q \leq 300000\)

Solution

题目只有两种操作,联通两个联通块,以及询问一个联通块内的k小值

联通块可以用并查集维护,k小值用平衡树查询

在这道题中,我们需要知道什么信息呢?

1. 我们要能找到一座岛对应的联通块,这个不难,并查集维护即可

2. 为了方便起见,我直接把\(n+1\)~\(n+n\)作为splay上的节点,前n个点分别作为n颗splay的根节点,但要注意,这都是虚点

3. 除此之外,我们还要为每个联通块建一个根节点,能通过联通块找到splay中 的节点,以及可以知道重要度为x的是哪座岛

for(rg int i=1;i<=n;i++) {    in(x); fa[i]=i; id[x]=i; //读入,重要度为x的是i岛    t[i+n].val=x; t[i+n].size=1;//splay中节点信息    t[i+n].f=i; root[i]=i+n; //第i个联通块}

对于插入,我们使用启发式合并,并查集中的按秩合并就是启发式合并,也就是把节点少的直接接到节点多的树上面以保证深度和复杂度

也就是说,insert操作中需要再传一个参数,就是我们要把x合并到y中的y

其实合并的实质是在y这棵splay上重新开节点(敲重点!!!),拥有我们要合并的节点全部信息

而对于查询与岛x相连的岛中第k重要的岛,我们可以直接找到x所在的并查集对应的splay的根节点,然后查询第k小就可以了

Code

#include
    
     #define il inline#define rg register#define lol long long#define Min(a,b) (a)<(b)?(a):(b)#define Max(a,b) (a)>(b)?(a):(b)using namespace std;const int N=1e6+10;void in(int &ans){    ans=0; int f=1; char i=getchar();    while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}    while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0', i=getchar();    ans*=f;}int n,tot,m,q;int fa[N],root[N],id[N];char s[5];struct Splay {    int f,size,ch[2],val;}t[N<<2];il bool get(int x) {    return t[t[x].f].ch[1]==x;}il void up(int x) {    t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;}void rotate(int x) {    int f=t[x].f,gf=t[f].f;    int k1=get(x),k2=get(f);    t[gf].ch[k2]=x,t[x].f=gf;    t[f].ch[k1]=t[x].ch[k1^1],t[t[x].ch[k1^1]].f=f;    t[x].ch[k1^1]=f,t[f].f=x;    up(f); up(x);}void splay(int x,int goal) {    while(t[x].f!=goal) {        int f=t[x].f,gf=t[f].f;        if(gf!=goal) get(x)^get(f)?rotate(x):rotate(f);        rotate(x);    }    if(goal<=n) root[goal]=x;//代表当前根不存在,我们给它赋一个值}void insert(int v,int rt) {    int u=root[rt],f=rt;    while(u && t[u].val!=v)        f=u,u=t[u].ch[v>t[u].val];    u=++tot;    if(f>n) t[f].ch[v>t[f].val]=u;//代表当前父节点是splay中的节点,存在    t[u].size=1; t[u].val=v;    t[u].ch[0]=t[u].ch[1]=0;    t[u].f=f; splay(u,rt);}int kth(int x,int k) {//x是并查集中的节点    int u=root[x]; if(t[u].size
     
      t[y].size+1)            u=t[u].ch[1],k-=t[y].size+1;        else if(k<=t[y].size) u=y;        else return t[u].val;    }}int find(int x) {    if(x!=fa[x]) fa[x]=find(fa[x]);    return fa[x];}void work(int x,int to) {    insert(t[x].val,to);    if(t[x].ch[0]) work(t[x].ch[0],to);    if(t[x].ch[1]) work(t[x].ch[1],to);}void merge(int x,int y) {    int r1=find(x),r2=find(y);    if(r1==r2) return;    if(t[root[r1]].size>t[root[r2]].size) swap(r1,r2);    fa[r1]=r2; work(root[r1],r2);}void query(int x,int y) {    int tq=kth(find(x),y);    printf("%d\n",tq==-1?-1:id[tq]);}int main(){    int x,y; in(n),in(m); tot=n+n;    for(rg int i=1;i<=n;i++) {        in(x); fa[i]=i;        id[x]=i; t[i+n].val=x;        t[i+n].size=1; t[i+n].f=i;        root[i]=i+n;    }    for(rg int i=1;i<=m;i++)         in(x),in(y),merge(x,y);    in(q);    for(rg int i=1;i<=q;i++) {        scanf("%s",s); in(x),in(y);        if(s[0]=='B') merge(x,y);        if(s[0]=='Q') query(x,y);    }    return 0;}
     
    

博主蒟蒻,随意转载.但必须附上原文链接