2611 問題 H: 藍(lán)橋杯2021年第十二屆省賽真題-雙向排序
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 3280 解決: 242
題目描述
給定序列 (a1, a2, · · · , an) = (1, 2, · · · , n)，即 ai = i。
小藍(lán)將對(duì)這個(gè)序列進(jìn)行 m 次操作，每次可能是將 a1, a2, · · · , aqi 降序排列，或者將 aqi , aqi+1, · · · , an 升序排列。
請(qǐng)求出操作完成后的序列。
輸入
輸入的第一行包含兩個(gè)整數(shù) n, m，分別表示序列的長度和操作次數(shù)。
接下來 m 行描述對(duì)序列的操作，其中第 i 行包含兩個(gè)整數(shù) pi, qi 表示操作類型和參數(shù)。當(dāng) pi = 0 時(shí)，表示將 a1, a2, · · · , aqi 降序排列；當(dāng) pi = 1 時(shí)，表示將 aqi , aqi+1, · · · , an 升序排列。
輸出
輸出一行，包含 n 個(gè)整數(shù)，相鄰的整數(shù)之間使用一個(gè)空格分隔，表示操作完成后的序列。
提示
【樣例說明】
原數(shù)列為 (1, 2, 3)。 第 1 步后為 (3, 2, 1)。 第 2 步后為 (3, 1, 2)。 第 3 步后為 (3, 1, 2)。與第 2 步操作后相同，因?yàn)榍皟蓚€(gè)數(shù)已經(jīng)是降序了。
【評(píng)測(cè)用例規(guī)模與約定】
對(duì)于 30% 的評(píng)測(cè)用例，n, m ≤ 1000；
對(duì)于 60% 的評(píng)測(cè)用例，n, m ≤ 5000；
對(duì)于所有評(píng)測(cè)用例，1 ≤ n, m ≤ 100000，0 ≤ ai ≤ 1，1 ≤ bi ≤ n。