#ABC234D. 前缀第 k 大

前缀第 k 大

AT_abc234_d [ABC234D] Prefix K-th Max

题目描述

\hspace{15pt}给定一个 1∼n1 \sim n 的排列 p={p1,p2,…,pn}p=\{p_1,p_2,\dots,p_n\},以及一个正整数 kk。

\hspace{15pt}这里,长度为 nn 的排列指由 1∼n1 \sim n 这 nn 个整数、按任意顺序组成的数组,其中每个整数恰好出现一次。

\hspace{15pt}对于每个 i=k,k+1,…,ni=k,k+1,\dots,n,请你求出 pp 的前 ii 项 p1,p2,…,pip_1,p_2,\dots,p_i 中第 kk 大的值。

\hspace{15pt}其中,一组数中的第 kk 大的值指将这组数从大到小排列后位于第 kk 个的数。由于 pp 是排列,前 ii 项中的数两两不同,因此第 kk 大的值是唯一的。

输入格式

\hspace{15pt}第一行输入两个整数 nn 和 $k \left(1 \leqq k \leqq n \leqq 5 \times 10^5\right)$ 分别代表排列的长度与要求的排名。

\hspace{15pt}第二行输入 nn 个整数 p1,p2,…,pn(1≦pi≦n)p_1,p_2,\dots,p_n \left(1 \leqq p_i \leqq n\right) 代表给定的排列。保证 p1,p2,…,pnp_1,p_2,\dots,p_n 两两不同。

输出格式

\hspace{15pt}输出 n−k+1n-k+1 行,第 jj 行输出 i=k+j−1i=k+j-1 时前 ii 项中第 kk 大的值。

测试样例

3 2
1 2 3
1
2

样例 1 解释

\hspace{15pt}排列为 p={1,2,3}p=\{1,2,3\},k=2k=2,需要依次处理 i=2i=2 和 i=3i=3:

∙ \hspace{23pt}\bullet\,当 i=2i=2 时,前 22 项为 {1,2}\{1,2\},从大到小排列为 {2,1}\{2,1\},第 22 大的值是 11;

∙ \hspace{23pt}\bullet\,当 i=3i=3 时,前 33 项为 {1,2,3}\{1,2,3\},从大到小排列为 {3,2,1}\{3,2,1\},第 22 大的值是 22。

\hspace{15pt}因此依次输出 11 和 22。

11 5
3 7 2 5 11 6 1 9 8 10 4
2
3
3
5
6
7
7