AT_abc234_d [ABC234D] Prefix K-th Max
题目描述
给定一个 1∼n 的排列 p={p1,p2,…,pn},以及一个正整数 k。
这里,长度为 n 的排列指由 1∼n 这 n 个整数、按任意顺序组成的数组,其中每个整数恰好出现一次。
对于每个 i=k,k+1,…,n,请你求出 p 的前 i 项 p1,p2,…,pi 中第 k 大的值。
其中,一组数中的第 k 大的值指将这组数从大到小排列后位于第 k 个的数。由于 p 是排列,前 i 项中的数两两不同,因此第 k 大的值是唯一的。
输入格式
第一行输入两个整数 n 和 $k \left(1 \leqq k \leqq n \leqq 5 \times 10^5\right)$ 分别代表排列的长度与要求的排名。
第二行输入 n 个整数 p1,p2,…,pn(1≦pi≦n) 代表给定的排列。保证 p1,p2,…,pn 两两不同。
输出格式
输出 n−k+1 行,第 j 行输出 i=k+j−1 时前 i 项中第 k 大的值。
测试样例
3 2
1 2 3
1
2
样例 1 解释
排列为 p={1,2,3},k=2,需要依次处理 i=2 和 i=3:
∙当 i=2 时,前 2 项为 {1,2},从大到小排列为 {2,1},第 2 大的值是 1;
∙当 i=3 时,前 3 项为 {1,2,3},从大到小排列为 {3,2,1},第 2 大的值是 2。
因此依次输出 1 和 2。
11 5
3 7 2 5 11 6 1 9 8 10 4
2
3
3
5
6
7
7