{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e区间套定理是实数完备性的一个重要基本定理。有关区间操作的题目也是算法题中一个很常见的题目类型。有关区间操作的算法也是算法学习中一类很重要的算法。\u003c/p\u003e\n\n\u003cp\u003e题意如下:\u003cp\u003e\n\n输入一个整数 $$$n$$$ 表示有一个 $$$n$$$ 项数组{$$$A_n$$$}(初始时所有元素都是 $$$0$$$),然后输入一个整数 $$$q$$$ 表示需要进行 $$$q$$$ 次操作。\u003cp\u003e\n\n第i次操作为任选一个区间 [$$$l_i$$$,$$$r_i$$$],将数组 {$$$A_n$$$} 从第 $$$l_i$$$ 到 $$$r_i $$$之间所有项(包括第 $$$l_i$$$ 和 $$$r_i$$$ 项)的值改为 $$$i$$$ 。$$$q$$$ 次操作必须全部执行并且必须保证区间中的每一项 $$$A_i$$$ 都至少被一个操作区间套住。\u003cp\u003e\n\n\u003cp\u003e\n问对于输入的一个 $$$n$$$ 项数列 {$$$a_n$$$},你是否能够通过 $$$q$$$ 次上述类型的操作将初始的数列 {$$$A_n$$$} 改为数列{$$$a_n$$$}? \n\n\u003cp\u003e\n若存在这样一个操作方案则输出\"\u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e\".,并输出最终得到的数组。(注意,若 $$$a_i$$$ 的值为 $$$0$$$,则输出的最终数组需将其替换为其它值,前提是符合某个合法方案的结果。结合样例更任意读懂题意。)\n\u003cp\u003e\n若不存在这样的操作方案则输出\"\u003cspan class\u003d\"tex-font-style-tt\"\u003eNO\u003c/span\u003e\".\n"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \\le n, q \\le 2 \\cdot 10^5$$$) — 表示数组项数和操作次数。\u003c/p\u003e\n\u003cp\u003e第二行输入 $$$n$$$ 个整数 $$$a_1, a_2, \\dots, a_n$$$ ($$$0 \\le a_i \\le q$$$) — 表示最终数组{$$$a_n$$$}。若 $$$a_i$$$ 为 $$$0$$$ 则表示第 $$$i$$$ 项可取任意可行值。\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e若需要输出 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e\" ,则输出 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e\" 后,还需要输出最终数组,每项用空格隔开。\u003cp\u003e否则输出 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eNO\u003c/span\u003e\".\u003c/p\u003e若有多种可行的最终数组,输出任意一种即可。\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3\n1 0 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\n1 2 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 10\n10 10 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\n10 10 10 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 6\n6 5 6 2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNO\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 4","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 5\n0 0 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\n5 4 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e第一个样例中的$$$0$$$ 可以用 $$$1$$$ 替代,然而不能用 $$$3$$$ 因为若将该项改为$$$3$$$,则势必第 $$$3$$$ 项也改为了 $$$3$$$,但其应该为 $$$2$$$。\u003c/p\u003e\n\u003cp\u003e第二个样例中,只需要第 $$$10$$$ 次操作覆盖整个数组即可。\u003c/p\u003e\n\u003cp\u003e第三个样例,无论这 $$$q$$$ 个操作区间如何框选都无法满足要求。因为“ 6 5 6 ”,第六次操作必然要将 $$$a_1 a_3$$$ 修改为 $$$6$$$ ,这样 $$$a_2$$$ 也会因此改为 $$$6$$$,而 $$$a_2$$$ 应该为 $$$5$$$。"}}]}