{"problem":{"name":"[GESP202409 四级] 区间排序","description":{"content":"小杨有一个包含 $n$ 个正整数的序列 $a$。 小杨计划对序列进行多次升序排序，每次升序排序小杨会选择一个区间 $[l,r]$（$l \\leq r$）并对区间内所有数字，即进行升序 $a_l, a_{l + 1}, \\dots a_r$ 排序。每次升序排序会在上一次升序排序的结果上进行。 小杨想请你计算出多次升序排序后的序列。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4041"},"statements":[{"statement_type":"Markdown","content":"小杨有一个包含 $n$ 个正整数的序列 $a$。\n\n小杨计划对序列进行多次升序排序，每次升序排序小杨会选择一个区间 $[l,r]$（$l \\leq r$）并对区间内所有数字，即进行升序 $a_l, a_{l + 1}, \\dots a_r$ 排序。每次升序排序会在上一次升序排序的结果上进行。\n\n小杨想请你计算出多次升序排序后的序列。\n\n## Input\n\n第一行包含一个正整数 $n$，含义如题面所示。   \n第二行包含 $n$ 个正整数 $a_1, a_2, \\dots a_n$，代表序列 $a$。  \n第三行包含一个正整数 $q$，代表排序次数。  \n之后 $q$ 行，每行包含两个正整数 $l, r$，代表将区间 $[l_i, r_i]$ 内所有数字进行升序排序。\n\n## Output\n\n输出一行包含 $n$ 个正整数，代表多次升序排序后的序列。\n\n[samples]\n\n## Background\n\n对应的选择、判断题：<https://ti.luogu.com.cn/problemset/1160>\n\n## Note\n\n### 样例 1 解释\n\n- 第一次升序排序后，序列为 $[3,4,5,1,2]$；\n- 第二次升序排序后，序列为 $[3,4,1,5,2]$；\n- 第三次升序排序后，序列为 $[1,3,4,5,2]$；\n\n### 数据规模与约定\n\n对于全部的测试数据，保证 $1 \\leq n, a_i, q \\leq 100$，$1 \\leq l_i \\leq r_i \\leq n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4041","tags":["模拟","2024","排序","GESP"],"sample_group":[["5\n3 4 5 2 1\n3\n4 5\n3 4\n1 3\n","1 3 4 5 2"]],"created_at":"2026-03-03 11:09:25"}}