C1028 - 移动盒子
题目描述
你有一行盒子，从左到右依次编号为1,2,3,…,n。可以执行以下4种指令:
① 1 X Y表示把盒子X移动到盒子Y左边（如果X已经在Y的左边则忽略此指令，指的是X紧挨着Y的情况，即XY）
② 2 X Y表示把盒子X移动到盒子Y右边（如果X已经在Y的右边则忽略此指令，指的是X紧挨着Y的情况，即YX）
③ 3 X Y表示交换盒子X和Y的位置
④ 4 表示反转整条链
指令保证合法，即X不等于Y。
例如，当n = 6时在初始状态下（1 2 3 4 5 6）执行1 1 4后，盒子序列为2 3 1 4 5 6。接下来执行2 3 5，盒子序列变成2 1 4 5 3 6。再执行3 1 6，得到2 6 4 5 3 1。最终执行4，得到1 3 5 4 6 2。
输入格式
输入包含1组数据，第一行为盒子个数n和指令条数m，以下m行每行包含一条指令。
输出格式
输出一行，即最终排列所有奇数位置的盒子编号之和。位置从左到右编号为1~n。
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| 6 4 1 1 4 2 3 5 3 1 6 4 |
12 |
| 6 3 1 1 4 2 3 5 3 1 6 |
9 |
| 100000 1 4 |
2500050000 |
输入输出样例解释
以第一组样例说明为例：
第1行：6 4，代表有6个盒子（初始排列为：1 2 3 4 5 6），4代表接下来有4条指令
第2行：1 1 4，代表将1盒子移动到4盒子的左边，执行完该指令后，排列为：2 3 1 4 5 6
第3行：2 3 5，代表将3盒子移动到5盒子的右边，执行完该指令后，排列为：2 1 4 5 3 6
第4行：3 1 6，代表将1盒子和6盒子交换，执行完该指令后，排列为：2 6 4 5 3 1
第5行：4，代表将整个排列反转一下，执行完该指令后，排列为：1 3 5 4 6 2
最后输出的是，最终排列的奇数位置的盒子编号之和（位置从左到右编号为1~n）：
1 + 5 + 6 => 12
最终输出结果为：12
注意数据比较大，需要用到long long去保存最终的结果
数据范围与提示
50%的数据：$1 \le n, m \le 100$
100%的数据：$1 \le n, m \le 10^{5}$
提示
本题难度较大，建议大家先用简单的方式（比如数组、vector这类的）先去拿到个部分分（50分）
如果时间、能力允许的条件下，可以冲个100分的做法
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式