← 返回题目列表

AtCoder · tupc2023_i

I. 最大化数组

中文机器翻译题面 查看原题

配点 : {100} 点

問題文

长度 小于或等于 N 的正整数序列 给出了 A=(A_1,A_2,\ldots,A_N) 和一个正整数 对 K 。 对于 A 重复以下操作任意多次,以找到最大的字典序数字序列。 删除

  • A 的长度 K 的连续子序列。严格来说,当前 A 的长度 M 作为整数 替换为 i\ (1\leq i\leq M-K+1) ,A=(A_1,A_2,\ldots,A_M) 该值应乘以 (A_1,\ldots,A_{i-1},A_{i+K},\ldots,A_{M}) 。

制約

  • 2\leq N\leq 3\times 10^5
  • 1\leq K\leq N-1
  • 1\leq A_{i}\leq N
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N K
A_1 A_2 \ldots A_N

出力

打印答案。 来自


入力例 1

9 3
1 2 3 4 1 2 3 4 1

出力例 1

4 4 1

这是允许您获取按字典顺序排列的最大数字序列的操作程序之一。

  • (1,2,3,4,\color{red}{1}\color{black},\color{red}{2}\color{black},\color{red}{3}\color{black},4,1) \to (\color{red}{1}\color{black},\color{red}{2}\color{black},\color{red}{3}\color{black},4,4,1)\to(4,4,1)

入力例 2

6 1
1 6 4 2 3 5

出力例 2

6 5

这是允许您获取按字典顺序排列的最大数字序列的操作程序之一。

  • (1,6,4,\color{red}2\color{black},3,5)\to(1,6,\color{red}4\color{black},3,5)\to(\color{red}1\color{black},6,3,5)\to(6,\color{red}3\color{black},5)\to(6,5)

入力例 3

6 5
6 5 4 3 2 1

出力例 3

6 5 4 3 2 1

最好不要操作它。