传送门:https://vjudge.net/contest/391081#problem/B
题意:给你一个数组A，对于 【长度 >= k 的所有子数组】 ，求第k大。将所有结果k存入B数组。问你B数组里的第M大数是多少。
思路：
这个题看上去好像很难。但是很显然一点：M过大,到1e10.大概率就是二分答案求了。
然后顺着这个思路.发现一个重要性质就好写了:左端点固定的第k大具有单调性.(联想区间最值的单调性)
那么对于一个确定的X,我们就可以用尺取 + 计数 在O(n)的时间内回答:A中有多少个区间符合 kth >= x.
ps : kth >= x 的条件 等价于 存在k个 >= x 的数.所以我们尺取的时候只需要记录个数cnt即可.不用数据结构维护.
然后对M二分答案.
然后还有一点:由于我们需要控制答案一定属于A数组.所以在二分答案的时候直接对A数组排序去重后得到B.在B上二分即可.
京公网安备 11010502036488号