#P6338. 不降序列

    ID: 6419 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>CF1500普及+/提高-序列构造分块构造

不降序列

题目描述

有一个长度为 nn 的未知整数序列 aa,每个元素都在 [1,m][1,m] 内。按如下过程从 aa 生成序列 bb。

开始时 bb 为空。依次处理 a1,…,ana_1,\ldots,a_n。处理 aia_i 时,若 bb 中存在严格大于 aia_i 的元素,就将从左到右第一个这样的元素替换为 aia_i。若不存在,将 aia_i 追加到 bb 的末尾。

给定 n,mn,m 和最终得到的长度为 kk 的序列 bb,判断是否存在合法的原序列 aa。若存在,输出任意一个。

输入格式

第一行三个正整数 n,m,kn,m,k。第二行 kk 个整数 b1,…,bkb_1,\ldots,b_k,保证 bb 非递减。

输出格式

若不存在合法的原序列,输出一行 No。若存在,先输出一行 Yes,再输出一行 nn 个整数,表示一组合法的原序列 aa。第二行的长度是 nn,与样例和评测检查器一致。

样例

4 10 3
3 7 7
Yes
3 7 10 7

原题另在下发文件中提供样例 2、3。

数据范围

1≤k≤n≤3×1051\le k\le n\le3\times10^5,1≤m≤1091\le m\le10^9,1≤bi≤m1\le b_i\le m,且 bb 非递减。

原子任务 分值 附加限制
1 20 n≤7n\le7,m≤10m\le10
2 n≤500n\le500
3 25 n≤5000n\le5000
4 20 n≤105n\le10^5
5 15 无

原 PDF 题面