Dotcpp  >  编程题库  >  蓝桥杯2021年第十二届省赛真题-双向排序
题目 2611:

蓝桥杯2021年第十二届省赛真题-双向排序

时间限制: 1s 内存限制: 128MB 提交: 2107 解决: 153

题目描述

给定序列 (a1, a2, · · · , an) = (1, 2, · · · , n),即 ai = i。
小蓝将对这个序列进行 m 次操作,每次可能是将 a1, a2, · · · , aqi 降序排列,或者将 aqi , aqi+1, · · · , an 升序排列。
请求出操作完成后的序列。

输入格式

输入的第一行包含两个整数 n, m,分别表示序列的长度和操作次数。
接下来 m 行描述对序列的操作,其中第 i 行包含两个整数 pi, qi 表示操作类型和参数。当 pi = 0 时,表示将 a1, a2, · · · , aqi 降序排列;当 pi = 1 时,表示将 aqi , aqi+1, · · · , an 升序排列。

输出格式

输出一行,包含 n 个整数,相邻的整数之间使用一个空格分隔,表示操作完成后的序列。

样例输入

3 3
0 3
1 2
0 2

样例输出

3 1 2

提示

【样例说明】
原数列为 (1, 2, 3)。 第 1 步后为 (3, 2, 1)。 第 2 步后为 (3, 1, 2)。 第 3 步后为 (3, 1, 2)。与第 2 步操作后相同,因为前两个数已经是降序了。
【评测用例规模与约定】
对于 30% 的评测用例,n, m ≤ 1000;
对于 60% 的评测用例,n, m ≤ 5000;
对于所有评测用例,1 ≤ n, m ≤ 100000,0 ≤ ai ≤ 1,1 ≤ bi ≤ n。
标签