求数组任意元素右边第 k 个比它小的元素
Preface
补 Codeforces Round 958 (Div. 2) E 题时,需要求得一个数组任意元素左右第 111 和第 222 个比它小的元素。
研究了 Jiangly 的写法,得到一个通用的解法,记录如下。
问题引入
我们都知道,如果我们想求得一个数组任意元素左边或右边的第一个比他大或小的元素,可以通过单调栈实现,时间和空间复杂度都是 O(n)O(n)O(n) 。但是如果我们想求得一个数组任意元素左边或右边的第 kkk 个比他大或小的元素,该怎么办呢?
解决思路
线段树 + 二分(线段树上二分优化)
我们考虑使用线段树来解决这个问题。我们可以用线段树来维护区间最小值,然后通过二分查找来找到第 iii 个比他小或大的元素的位置,共 kkk 次二分查找,时间复杂度为 O(nklog2n)O(nk\log^2 n)O(nklog2n) 。
考虑线段树上二分优化,可以消去一层二分,时间复杂度为 O(nklogn)O(nk\log n)O(nklogn) 。
这样,我们就得到了时间复杂度为 O(nklogn)O(nk\log n)O(nklogn) 的解法。
但是这种解法 ...
Ciallo~(∠・ω< ) World!
Ciallo~(∠・ω< ) World!