Tokitsukaze and Kth Problem (easy)

首先，二元组有个，肯定不可能直接枚举，因此我们应该考虑尝试使用其他方法。

题解有二分的方法我觉得非常合适，在赛时我使用的是priority_queue来完成前k大元素的遍历。

首先，我们可以将数组中的元素全部对取模，然后再按从小到大排序。这样我们得到的。

接下来我们要思考：如何去搜索到前k大的值呢？那么我们首先要明白有哪些二元组是“潜在”的最大值。

我们可以发现，首先，是最大的，也就是最接近的元素，因此可能是一个潜在的最大值。还有哪些？

对于每一个元素，是不是可能存在一个元素，使得

呢？也就是说，是满足最大的下标。它是不是也有可能是最大元素？

对于每一个，我们都可以用lower_bound或upper_bound寻找到，那我们现在是不是有了个可能的最大元素。我们把它们按照从大到小放入priority_queue中。

接下来如何搜索呢？对于priority_queue中的每一个元素，是不是只能往和的方向搜索呢？显然是的。

因为如果你取或者，那么就很容易，在模意义下就会变为0，搜索方向显然是错的。因此，我们只能选择往和的方向搜索。

那么：

  1. 往这个方向搜索是否能保证不重不漏呢？

    答案是肯定的。因为这样的话的值只能减小，且由于初始时对于每一个都放入了堆中，因此每个位置开始的最大值都被放入了堆中，确保了搜索的正确性。最关键的是我们在堆中放入了一个元素，保证了在的部分也得到了搜索。

    至于重复，我们需要用一个set或者unordered_set记录已经搜索过的二元组（类似于vis数组），因此，在搜索到相同的二元组时跳过。

  2. 堆里不停地添加元素，时间复杂度不会爆炸吗？

    根据我们的操作，初始时堆中的元素为个（准确来说是个），而每次遍历都会弹出一个堆中的元素，加入至多2个元素，且，因此最多操作次，每次操作堆中最多添加1个元素，那么堆中最多也只会有个元素。每次操作都是级别的。由于同阶，因此保证了时间复杂度为。

AC代码

几乎一模一样的练习题：ABC391-F K-th Largest Triplet