HM207 双端月台装卸

来源： 第 207 集 deque容器-插入和删除

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

双端月台的装卸分两类。

两端操作：往里推数据都叫 push，往外弹数据都叫 pop；尾部叫 back，头部叫 front。因此：

• push_back 尾插，push_front 头插；
• pop_back 尾删，pop_front 头删。

指定位置操作必须提供迭代器，不能把 \(0,1,2\) 这种下标直接传进去。可以把迭代器先取出来再偏移，例如 it = begin(); it++; 后再 erase(it)，删的就是第二个元素。

• insert(begin()+p, x)：在偏移 \(p\) 插入一个值。
• insert(begin()+p, k, x)：插入 \(k\) 个相同值。
• insert(begin()+p, a.begin(), a.end())：把另一座月台上的一段区间插进来。
• erase(begin()+p)：删除一个元素。
• erase(begin()+L, begin()+R)：删除半开区间；若区间是 \([0,\textit{size})\)，效果类似清空。
• clear()：专门用来清空。

从空月台开始执行 \(q\) 条指令，**每条指令后输出一次**当前序列。打印使用 const 引用和 const_iterator。

输入格式

第一行一个整数 \(q\)。

接下来 \(q\) 行，每行一条指令：

• 1 x：push_back(x)
• 2 x：push_front(x)
• 3：pop_back()（保证非空）
• 4：pop_front()（保证非空）
• 5 p x：在偏移 \(p\) 插入一个 \(x\)
• 6 p k x：在偏移 \(p\) 插入 \(k\) 个 \(x\)
• 7 p m 然后 \(m\) 个整数：先把这 \(m\) 个数放进临时月台，再在偏移 \(p\) 插入这段区间
• 8 p：删除偏移 \(p\) 处的元素（实现时应先做出迭代器再偏移，再 erase）
• 9 L R：删除半开区间 \([L,R)\)
• 10：clear()

输出格式

共 \(q\) 行。每行用单个空格分隔当前全部整数，行末无多余空格。空月台输出空行。

样例

输入 #1

10
1 10
1 20
2 100
2 200
3
4
5 0 1000
6 0 2 10000
7 0 3 1 2 3
8 1

输出 #1

10
10 20
100 10 20
200 100 10 20
200 100 10
100 10
1000 100 10
10000 10000 1000 100 10
1 2 3 10000 10000 1000 100 10
1 3 10000 10000 1000 100 10

输入 #2

7
1 10
1 20
2 100
2 200
8 1
9 0 3
10

输出 #2

10
10 20
100 10 20
200 100 10 20
200 10 20

说明

\(1 \le q \le 200\)，\(0 \le k,m \le 100\)，元素绝对值不超过 \(10^9\)。保证每条指令合法。

样例 #1 对应「两端装卸 + 三种 insert + 偏移后删第二个元素」。样例 #2 在 200 100 10 20 上先把迭代器从 begin 偏移一次再删除，剩下 200 10 20，再按区间清空。