{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDreamGrid正在学习LIS(最长递增子序列)问题,他需要找到给定长度为$n$的序列$a_1, a_2, \\dots, a_n$的最长递增子序列。\u003c/p\u003e\n\n\u003cp\u003e\n回想一下\n\u003c/p\u003e\u003cul\u003e\n\u003cli\u003e\u003cp\u003e长度为$m$的子序列$b_1, b_2, \\dots, b_m$是满足$b_1 \u003d a_{k_1}, b_2 \u003d a_{k_2}, \\dots, b_m \u003d a_{k_m}$和$1 \\le k_1 \u0026lt; k_2 \u0026lt; \\dots \u0026lt; k_m \\le n$的序列。\u003c/p\u003e\u003c/li\u003e\n\u003cli\u003e\u003cp\u003e递增子序列$b_1, b_2, \\dots, b_m$是满足$b_1 \u0026lt; b_2 \u0026lt; \\dots \u0026lt; b_m$的子序列。\u003c/p\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003eDreamGrid定义了辅助序列$f_1, f_2, \\dots, f_n$,其中$f_i$表示以$a_i$结尾的最长递增子序列的长度。如果你不知道如何推导辅助序列,他提供了以下伪代码,用于计算辅助序列。\u003c/p\u003e\n\n\u003cp style\u003d\"border: 1px solid black; float: left; margin-left: 100px; padding: 10px;\"\u003e\n\u003cb\u003eprocedure\u003c/b\u003e lis_helper($a$: 原始序列)\u003cbr\u003e\n{令$n$为原始序列的长度,\u003cbr\u003e\n$f(i)$为序列$f$的第$i$个元素,\u003cbr\u003e\n$a(i)$为序列$a$的第$i$个元素}\u003cbr\u003e\n\u003cb\u003efor\u003c/b\u003e $i$ :\u003d 1 \u003cb\u003eto\u003c/b\u003e $n$\u003cbr\u003e\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;$f(i)$ :\u003d 1\u003cbr\u003e\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003cb\u003efor\u003c/b\u003e $j$ :\u003d 1 \u003cb\u003eto\u003c/b\u003e ($i$ - 1)\u003cbr\u003e\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003cb\u003eif\u003c/b\u003e $a(j) \u0026lt; a(i)$ \u003cb\u003eand\u003c/b\u003e $f(j) + 1 \u0026gt; f(i)$\u003cbr\u003e\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;$f(i)$ :\u003d $f(j)$ + 1\u003cbr\u003e\n\u003cb\u003ereturn\u003c/b\u003e $f$ {$f$是辅助序列}\u003cbr\u003e\n\u003c/p\u003e\n\n\u003cdiv style\u003d\"clear: both;\"\u003e\u003c/div\u003e\n\n\u003cp\u003eDreamGrid已经使用该程序推导出了辅助序列,但原始序列$a_1, a_2, \\dots, a_n$被BaoBao偷走了,现在已经丢失!DreamGrid现在手头上只有辅助序列和两个范围序列$l_1, l_2, \\dots, l_n$和$r_1, r_2, \\dots, r_n$,表示所有$1 \\le i \\le n$。\u003c/p\u003e\n\n\u003cp\u003e请帮助DreamGrid恢复与辅助序列和两个范围序列兼容的原始序列。\u003c/p\u003e\n\n\u003ch4\u003e输入\u003c/h4\u003e\n\u003cp\u003e有多个测试用例。输入的第一行包含一个整数$T$,表示测试用例的数量。对于每个测试用例:\u003c/p\u003e\n\n\u003cp\u003e第一行包含一个整数$n$($1 \\le n \\le 10^5$),表示原始序列的长度。\u003c/p\u003e\n\n\u003cp\u003e第二行包含$n$个整数$f_1, f_2, \\dots, f_n$($1 \\le f_i \\le n$),用空格分隔,表示辅助序列。\u003c/p\u003e\n\n\u003cp\u003e对于接下来的$n$行,第$i$行包含两个整数$l_i$和$r_i$($0 \\le l_i \\le r_i \\le 2 \\times 10^9$),表示范围序列。\u003c/p\u003e\n\n\u003cp\u003e保证原始序列存在,并且所有测试用例的$n$之和不会超过$5 \\times 10^5$。\u003c/p\u003e\n\n\u003ch4\u003e输出\u003c/h4\u003e\n\u003cp\u003e对于每个测试用例,输出一行,包含$n$个用空格分隔的整数,表示原始序列。如果有多个有效答案,则打印其中任意一个。\u003c/p\u003e\n\n\u003cp\u003e请不要在每行末尾打印额外的空格,否则你的解决方案可能会被视为不正确!\u003c/p\u003e\n\n\u003ch4\u003e示例\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e4\n6\n1 2 3 2 4 3\n0 5\n2 4\n3 3\n1 2\n3 5\n1 5\n5\n1 2 1 3 1\n100 200\n200 300\n200 400\n400 500\n100 500\n7\n1 2 3 1 1 4 2\n0 3\n0 3\n0 3\n0 3\n0 3\n0 3\n0 3\n2\n1 1\n1 2\n2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2 3 2 5 3\n200 300 200 500 200\n0 1 2 0 0 3 1\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}