Prefix K-th Max

题目描述

给定一个排列 $P=(P_1,P_2,\ldots,P_N)$，它是 $(1,2,\ldots,N)$ 的一个排列，以及一个正整数 $K$。 对于每个 $i=K,K+1,\ldots,N$，求以下值。

在 $P$ 的前 $i$ 个项中第 $K$ 大的值。

输入格式

输入从标准输入按以下格式给出： $N$ $K$ $P_1$ $P_2$ $\ldots$ $P_N$

输出格式

对于每个 $i=K, K+1, \ldots, N$，按此顺序输出题目陈述中要求的值，每个值占一行。

3 2
1 2 3

1
2

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

2
3
3
5
6
7
7

提示

$1 \leq K \leq N \leq 5 \times 10^5$ $(P_1,P_2,\ldots,P_N)$ 是 $(1,2,\ldots,N)$ 的一个排列。 输入中的所有值都是整数。在前两个项 $(P_1,P_2)=(1,2)$ 中的第 $(K=)$ $2$ 大值是 $1$。 在前三个项 $(P_1,P_2,P_3)=(1,2,3)$ 中的第 $(K=)$ $2$ 大值是 $2$.

标签: AtCoder|abc234D

来源

AtCoder|abc234D