F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5214. -- 可持久化权值妹子树

5214: 可持久化权值妹子树

Time Limit: 15 Sec  Memory Limit: 700 MB
Submit: 98  Solved: 9
[Submit][Status][Discuss]

Description

小y有n个妹子,编号分别为1, 2,... n。为了更好管理这些妹子,小y想把他们分成若干组~
在开始的开始(我们记作分组方案0)中,每个妹子各成一组。
每次小y会选择一个已有的分组方案i,挑出其中两个不在同组的妹子x, y,将她们所在的组合并。
我们将第j次操作得到的分组方案记作分组方案j。这样就可以得到许多不同的分组方案啦!
为了知道这些分组方案孰优孰劣,因此小y想知道关于分组方案的一些信息。
每次,小y会选择某一个分组方案i,询问x所在的组中编号第k小的妹子是谁。
为了小y的幸福(划掉),来帮帮他把(逃

Input

第一行两个整数n, m。表示妹子数和操作数。
接下来的m行,首先有一个整数opt。
如果opt=0,接下来三个整数i, x, y,表示一次合并。保证分组方案i已经出现过,x, y在不同组中。
如果opt=1,接下来三个整数i, x, k,表示一次询问。保证x所在的组中至少有k个妹子。
1 <=n, q <= 100000,合并不超过60000次,询问不超过60000次

Output

对于每个询问操作输出一个整数,表示该妹子的编号

Sample Input

3 6
0 0 1 2
1 1 1 2
1 1 2 1
0 1 2 3
0 1 1 3
1 3 3 2

Sample Output

2
1
2

HINT

Source

Awd上传

[Submit][Status][Discuss]

HOME Back