題目 2611:
藍(lán)橋杯2021年第十二屆省賽真題-雙向排序
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 3280 解決: 242
題目描述
給定序列 (a1, a2, · · · , an) = (1, 2, · · · , n)，即 ai = i。
小藍(lán)將對這個(gè)序列進(jìn)行 m 次操作，每次可能是將 a1, a2, · · · , aqi 降序排列，或者將 aqi , aqi+1, · · · , an 升序排列。
請求出操作完成后的序列。
輸入格式
輸入的第一行包含兩個(gè)整數(shù) n, m，分別表示序列的長度和操作次數(shù)。
接下來 m 行描述對序列的操作，其中第 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)是降序了。
【評測用例規(guī)模與約定】
對于 30% 的評測用例，n, m ≤ 1000；
對于 60% 的評測用例，n, m ≤ 5000；
對于所有評測用例，1 ≤ n, m ≤ 100000，0 ≤ ai ≤ 1，1 ≤ bi ≤ n。
標(biāo)簽