本题要求在动态添加双向参见关系的笔记本页码中,支持查询指定页码的直接参见页码中编号第 k 大的页码。关键信息是 k≤10,且 n,q≤105,因此需要每个操作尽量接近常数时间。
解题思路如下:
set / unordered_set),用于存储当前所有直接参见的页码,以快速判断重复关系。vector / list),按升序保存该页码直接参见页码中编号最大的至多 10 个页码。因为查询只关心第 k 大(k≤10),只需保留前 10 大即可。小 A 有一本笔记本,总共有 n 个页码,依次编号为 1 到 n。他常常在两个页码之间添加互相参见的标记,使得它们可以直接跳转。每次添加标记都是双向的:即如果页码 u 和 v 互相参见,那么从 u 可以直接查阅 v,反之亦然;重复的标记不会生效。
现在你需要设计一个程序,支持以下两种操作:
约束:页码总数 n 和操作总数 q 均满足 1≤n,q≤105;k≤10;所有页码编号均为 1 到 n 的整数。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.