P11745 Dynamic K-th Problem
Kingna
·
·
题解
Subtask #1~2
考虑 O(Qn^2\log n) 的暴力，期望得分 20 分。
Subtask #7
## Subtask #4~5
询问的是一个后缀，直接预处理。考虑第 $k$ 大值至多 $n$ 种，那么对每一个 $a_i$ 处理出有多少个区间的第 $m$ 大值为 $a_i$，则等于 $a_i$ 的区间个数就可以求解。查询的时候，直接二分寻找答案。
考虑到区间 $[l,r]$ 用 $a_i$ 作为第 $m$ 大值，那么区间 $[l,r]$ 中就恰好有 $m-1$ 个数大于 $a_i$。那么我们找到比 $a_i$ 大的位置。可能有下列 $m$ 种情况：
* 左边有 $m-1$ 个比 $a_i$ 大，右边有 $0$ 个比 $a_i$ 大。
* 左边有 $m-2$ 个比 $a_i$ 大，右边有 $1$ 个比 $a_i$ 大。
* 以此类推。左边有 $0$ 个比 $a_i$ 大，右边有 $m-1$ 个比 $a_i$ 大。
不难发现，还需要解决区间长度大于等于 $K$ 的问题。这等价于左端点从 $[L_1,R_1]$ 中选择，右端点从 $[L_2,R_2]$ 中选择，区间长度大于等于 $K$ 的选择方案数。可以用数学方法在 $O(1)$ 时间内求解。
现在只需要找到比 $a_i$ 大的位置。如果花费 $O(\log n)$ 时间去找每一个位置，比如 ST 表或线段树，则总复杂度为 $O(nm\log n)$。期望得分 $56$。
## Subtask #8
用链表存储所有数字。按照 $a_i$ 从小到大扫的顺序，如果当前 $a_i$ 计算完毕，直接从链表中删除。此时链表中剩余的数字就是大于 $a_i$ 的数。
查找比 $a_i$ 大的位置时，只需要左跳右跳就行。复杂度 $O(nm)$。
期望得分 $100$。