HM219 链表装卸

来源： 第 219 集 list容器-插入和删除

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

链表可以在两端插删，也可以按迭代器指定位置插删，还可以按值一次删光所有相等元素。使用前包含头文件 list。打印时用 const 引用和 const_iterator。

两端：

• push_back / push_front：尾插、头插；
• pop_back / pop_front：尾删、头删。

指定位置必须提供迭代器，不能把 \(0,1,2\) 当下标直接传给 insert / erase。先取出迭代器再连续 ++：

• insert(it, x)：在该处插入一个值；
• insert(it, k, x)：插入 \(k\) 个相同值；
• insert(it, a.begin(), a.end())：插入另一段区间；
• erase(it)：删除一个节点；
• erase(left, right)：删除半开区间。

按值删除用 remove(x)：容器里**所有**等于 \(x\) 的元素都会被删掉，不必提供迭代器。clear() 清空全部。

从空链表开始执行 \(q\) 条指令，**每条指令后输出一次**当前序列。

输入格式

第一行一个整数 \(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\) 个整数：先放进临时链表，再在偏移 \(p\) 插入这段区间
• 8 p：删除偏移 \(p\) 处的节点
• 9 L R：删除半开区间 \([L,R)\)
• 10 x：remove(x)，删光所有 \(x\)
• 11：clear()

输出格式

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

样例

输入 #1

10
1 10
1 20
1 30
2 100
2 200
2 300
3
4
5 1 1000
8 0

输出 #1

10
10 20
10 20 30
100 10 20 30
200 100 10 20 30
300 200 100 10 20 30
300 200 100 10 20
200 100 10 20
200 1000 100 10 20
1000 100 10 20

输入 #2

8
1 1
1 2
1 2
1 3
10 2
6 1 2 9
7 0 2 8 8
11

输出 #2

1
1 2
1 2 2
1 2 2 3
1 3
1 9 9 3
8 8 1 9 9 3

说明

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

样例 #1：先尾插 \(10\,20\,30\)，再头插 \(100\,200\,300\)，得到 \(300\,200\,100\,10\,20\,30\)；尾删掉 \(30\)，头删掉 \(300\)；在偏移 \(1\) 插入 \(1000\)，再删掉开头。样例 #2：remove(2) 会一次删掉两个 \(2\)；最后 clear 后该行只输出换行。