一、题意

一个1...n的序列。（n<=100000）
有4中指令：
1 X Y 表示把X移动到Y的左边
2 X Y 表示把X移动到Y的右边
3 X Y 表示交换X和Y的位置
4 表示反转序列
输出最终序列的奇数位上的数字和，下标从1开始计算。

二、解析

用列表list模拟。
主要是要维护每个元素所在的位置，因此需要维护一个存放迭代器的pos[maxn]数组。
反转序列不需要真的反转，只需要用一个bool变量标记即可，同时注意左右的含义要根据这个标记进行变换。

三、代码

#include <iostream>
#include <list>
#include <iterator>
using namespace std;
const int maxn = 100000 + 5;
list<int> lst;
list<int>::iterator pos[maxn];
int kase = 1;

int main() {
    int n, q;
    while(cin >> n >> q) {
        lst.clear();
        for(int i = 1; i <= n; i ++) pos[i] = lst.insert(lst.end(), i);
        bool rev = 0;
        while(q --) {
            int ord, x, y;
            cin >> ord;
            if(rev) {
                if(ord == 1) ord = 2;
                else if(ord == 2) ord = 1;
            }
            switch (ord){
                case 1:
                    cin >> x >> y;
                    lst.erase(pos[x]);
                    pos[x] = lst.insert(pos[y], x);
                    break;
                case 2:
                    cin >> x >> y;
                    lst.erase(pos[x]);
                    pos[x] = lst.insert(next(pos[y]), x);
                    break;
                case 3:
                    cin >> x >> y;
                    iter_swap(pos[x], pos[y]);
                    swap(pos[x], pos[y]);
                    break;
                case 4:
                    rev = !rev;
            }
        }
        if(rev) lst.reverse();
        long long ans = 0;
        bool odd = 1;
        for(int num : lst) {
            if(odd) ans += num;
            odd = !odd;
        }
        cout << "Case " << kase ++ << ": " << ans << endl;
    }
}

四、归纳

  • 从这一题可以发现，insert操作不会破坏其它元素的迭代器，只是会改变迭代器的前后关系而已，通过insert的返回值为新元素的迭代器这一点，就可以很清晰地保持迭代器逻辑的完好。
  • iter_swap()交换两个迭代器所指向的值
  • 通过标记法来避免不必要的操作，如本题的反转操作。