P3224 [HNOI2012]永无乡

    • 478通过
    • 1.1K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 Splay 平衡树 2012 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    永无乡包含 $n$ 座岛,编号从 $1$ 到 $n$ ,每座岛都有自己的独一无二的重要度,按照重要度可以将这 $n$ 座岛排名,名次用 $1$ 到 $n$ 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛到达另一个岛。如果从岛 $a$ 出发经过若干座(含 $0$ 座)桥可以 到达岛 $b$ ,则称岛 $a$ 和岛 $b$ 是连通的。

    现在有两种操作:

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

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

    输入输出格式

    输入格式:

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

    接下来的一行是用空格隔开的 $n$ 个数,依次描述从岛 $1$ 到岛 $n$ 的重要度排名。随后的 $m$ 行每行是用空格隔开的两个正整数 $a_i$ 和 $b_i$ ,表示一开始就存在一座连接岛 $a_i$ 和岛 $b_i$ 的桥。

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

    输出格式:

    对于每个 Q x k 操作都要依次输出一行,其中包含一个整数,表示所询问岛屿的编号。如果该岛屿不存在,则输出 $-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 $

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。