P3224 [HNOI2012]永无乡（平衡树合并）

题目描述

永无乡包含 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 。

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

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

n≤100000,m≤n,q≤300000

思路平衡树合并把两个平衡树中小的那个拆开每一个加入到大的平衡树中

细节本蒟蒻在这个地方出错了 2个平衡树用并差集合并后其父节点既不是x也不是y也不是 find（x）也不是find（y）是小的平衡树想大的平衡树里加的最后一个元素那个元素是新的平衡树的新的根节点

#include<iostream>

#include<cstring>

#include<stdio.h>

using namespace std;

const int maxn  = +;

int f[maxn],val[maxn];

void init(){for(int i=;i<maxn;i++)f[i]=i;}

int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

int fa[maxn],ch[maxn][],root,siz[maxn];

int data[maxn];

void pushup(int x){siz[x]=siz[ch[x][]]+siz[ch[x][]]+;}

void pushdown(int x){}

void rorate(int x){

    int f=fa[x],df=fa[f],kind=ch[fa[x]][]==x;

    pushdown(f),pushdown(x);

    ch[f][kind]=ch[x][kind^];fa[ch[f][kind]]=f;

    ch[x][kind^]=f;fa[f]=x;fa[x]=df;

    if(df)ch[df][ch[df][]==f]=x;

    pushup(f);pushup(x);

}

void splay(int x,int tar){

    for(int f;(f=fa[x])!=tar;rorate(x))

        if(fa[f]!=tar){

            if((ch[fa[f]][]==f)==(ch[fa[x]][]==x))

              rorate(f);

            else  rorate(x);

        }

    if(!tar)root=x;

}

void insert(int x,int u)

{

    int ff=;

    while(u){ff=u;u=ch[u][val[x]>val[u]];}

    if(ff)ch[ff][val[x]>val[ff]]=x;

    fa[x]=ff;siz[x]=;

    ch[x][]=ch[x][]=;

    splay(x,);

}

int temdata[maxn],cnt=;

void getall(int x){

    if(ch[x][])getall(ch[x][]);

    temdata[cnt++]=x;

    if(ch[x][])getall(ch[x][]);

}

void merge(int x,int y)

{

    if(find(x)==find(y))return;

    x=find(x),y=find(y);

    if(siz[x]<siz[y])swap(x,y);

    cnt=;getall(y);

    for(int i=;i<cnt;i++)insert(temdata[i],x);

    f[x]=f[y]=temdata[cnt-];

}

int find_k(int x,int k){

    if(siz[x]<k)return -;

    if(siz[ch[x][]]+==k)return x;

    if(siz[ch[x][]]>=k)return find_k(ch[x][],k);

    return find_k(ch[x][],k-siz[ch[x][]]-);

}

int main()

{

    init();

    for(int i=;i<maxn;i++)siz[i]=;

    int N,M,Q,x,y;char op[];

    scanf("%d%d",&N,&M);

    for(int i=;i<=N;i++)scanf("%d",val+i);

    while(M--){

        scanf("%d%d",&x,&y);

        merge(x,y);

    }

    scanf("%d",&Q);

    while(Q--){

        scanf("%s%d%d",op,&x,&y);

        if(op[]=='Q')printf("%d\n",find_k(find(x),y));

        else merge(x,y);

    }

    return ;

}

巴特西

P3224 [HNOI2012]永无乡（平衡树合并）

题目描述

输入输出格式

最新文章

热门文章