题目名称 1341. [HNOI2012]永无乡
输入输出 bzoj_2733.in/out
难度等级 ★★★☆
时间限制 10000 ms (10 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2013-04-03
开放分组 全部用户
提交状态
分类标签
通过:105, 提交:298, 通过率:35.23%
Gravatar真呆菌 100 0.562 s C++
GravatarYoungsc 100 0.682 s C++
Gravatar落痕 100 0.708 s C++
Gravatarhzoi2017_nzy 100 0.715 s C++
GravatarAAAAAAAAAA 100 0.718 s C++
Gravatarzhhe0101 100 0.726 s C++
Gravatar... 100 0.737 s C++
Gravatarniconicoqaq 100 0.749 s C++
Gravatar半汪 100 0.755 s C++
Gravataryymxw 100 0.772 s C++
关于 永无乡 的讨论
Splay很容易就写挂掉。。。
GravatarQhelDIV
2013-04-05 11:17 1楼
像我这种弱菜也就刷点这水题了。。。
4kb程序。。。。一遍过。。。也不枉我改这么久。。。。
GravatarGDFRWMY
2014-01-26 12:23 2楼
回复 @Gold Miner :
神犇为何要卖萌
Gravatarcstdio
2014-01-26 12:57 3楼
我把rotate操作去掉了怎么还快一些。。ShenMeGui
GravatarHouJikan
2015-01-12 21:31 4楼
splay,2.2kb,时间四十分钟,这就是我的极限速度了吗……
Gravatar水中音
2015-03-15 15:45 5楼
Gravatar天一阁
2015-03-28 14:59 6楼
好吧 io优化是我粘的智神的= =
Gravatar真呆菌
2015-04-02 20:13 7楼
maya这题数据貌似裸的非递归bst可完爆treap?
Gravatarnew ioer
2015-04-13 15:44 8楼
暴力Merge??
Gravatarstdafx.h
2015-12-19 08:07 9楼
建议修改时限。。手一抖为毛连交3次 woc 300s..
Gravatarzzzzzfy
2016-01-19 19:52 10楼
我又忘了maintain不能用作函数名了。。。
Gravatarliu_runda
2016-05-09 15:14 11楼
回复 @liu_runda :
+1
Gravatarprefect1999
2016-07-06 21:54 12楼
GravatarAntiLeaf
2017-05-25 16:03 13楼
哇,并查集+平衡树!!弱弱的问句,当建新桥,除了把一个岛屿群逐个删掉再加到另一个岛屿群里去外,还有别的好方法吗?
Gravatar_Itachi
2016-08-03 14:14 14楼
回复 @波风水门大招旋闪光超轮舞吼叁式 :
不需要删掉啊...直接按照某种顺序遍历较小的树的同时把对应节点复制一份插入大树里就行...
参见我的代码...我用的是按照先序遍历顺序逐个插入...
GravatarAntiLeaf
2016-08-03 17:31 15楼
果然SBT好写几乎不用改,只要过了样例再把数组开大点就过了
Gravatar_Itachi
2016-08-05 19:08 16楼
1A这大水题
调了一节课发现是求值求错了,启发式合并没写挂
GravatarGo灬Fire
2016-12-12 10:32 17楼
无旋treap搞过...
Gravatarsxysxy
2016-12-12 11:58 18楼
向量数组不能用int&,否则会返回错误位置。
GravatarFoolMike
2016-12-12 16:14 19楼
并查集 + BST直接过
GravatarWeiSama
2017-03-12 10:24 20楼
好惨好惨……
调了一天……结果发现一个转的方向错了……身败名裂……
GravatarHZOI_蒟蒻一只
2017-05-25 08:49 21楼
线段树合并可以做到O(nlogV)的时间空间复杂度……
终于掌握了Treap的合并算法
GravatarFoolMike
2017-08-24 11:23 22楼
线段树合并
GravatarAAAAAAAAAA
2018-01-17 18:56 23楼
启发式的Splay跑的貌似有点慢
好吧 ,我的SB线段树更慢(雾
GravatarHT008
2018-03-23 10:26 24楼

1341. [HNOI2012]永无乡

★★★☆   输入文件:bzoj_2733.in   输出文件:bzoj_2733.out   简单对比
时间限制:10 s   内存限制:128 MB

【题目描述】

永无乡包含 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 行每行是用空格隔开的两个正整数 ai 和 bi,表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作,该部分的第一行是一个正整数 q, 表示一共有 q 个操作,接下来的 q 行依次描述每个操作,操作的格式如上所述,以大写字母 Q 或B 开始,后面跟两个不超过 n 的正整数,字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 n≤1000,q≤1000
 
对于 100%的数据 n≤100000,m≤n,q≤300000 
 

【输出格式】

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

【提示】


【来源】

【题目来源】

耒阳大世界(衡阳八中) OJ 2733