uva -12657 Boxes in a Line(双向链表)

题目链接

题意 ：$1$ ~ $n$的数字原本按顺序摆好，接下来有四种操作。

• $1XY$ ：将$X$移动到$Y$的左边
• $2XY$ ：将$X$移动到$Y$的右边
• $3XY$ ：交换$X,Y$的位置
• $4$ ：翻转整个数字串
  经过这一系列操作后，最后输出奇数位上的数字和。

题解 ：有移动到左右的操作，所以想到了双向链表。由于是第一次写双向链表，写得很精污。注意 ${\sum }_{i=1}^{100000}$会超出int范围，所以用$longlong$。在交换$X,Y$的位置的时候，要特判两个数字的位置是不是相邻的。

#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int maxn = 1e5 + 7;map<int, int> mp;
int n, m, op, x, y, l[maxn][2], cas;void init() {
    l[0][1] = 1;l[n + 1][0] = n;for (int i = 1; i <= n; ++i) {
    l[i][0] = i - 1;l[i][1] = i + 1;}mp[1] = 0, mp[2] = 1;
}void insert(int op, int x, int y) {
    if (l[y][op] == x) return;l[l[x][1]][0] = l[x][0];l[l[x][0]][1] = l[x][1];l[l[y][op]][op ^ 1] = x;l[x][op] = l[y][op];l[x][op ^ 1] = y;l[y][op] = x;
}void exc(int x, int y) {
    int ll = l[x][0], lr = l[x][1];int rl = l[y][0], rr = l[y][1];if (lr == y) {
    l[ll][1] = y;l[y][1] = x;l[y][0] = ll;l[x][0] = y;l[x][1] = rr;l[rr][0] = x;return;}if (ll == y) {
    l[rl][1] = x;l[x][1] = y;l[x][0] = rl;l[y][0] = x;l[y][1] = lr;l[lr][0] = y;return;}l[ll][1] = y, l[lr][0] = y;l[rl][1] = x, l[rr][0] = x;l[x][0] = rl;l[x][1] = rr;l[y][0] = ll;l[y][1] = lr;}void print(int op) {
    int head;ll res = 0;if (op) head = 0;else head = n + 1;int f = n, cnt = 1;while (f--) {
    head = l[head][op];if (cnt & 1) res += head;cnt ^= 1;}printf("Case %d: %lld\n", ++cas, res);
}void solve() {
    init();while (m--) {
    scanf("%d", &op);if (op == 4) {
    mp[1] ^= 1;mp[2] ^= 1;continue;}scanf("%d %d", &x, &y);if (op == 3) {
    exc(x, y);}else {
    insert(mp[op], x, y);}}print(mp[2]);
}
int _T;
int main() {
    while (~scanf("%d %d", &n, &m)) solve();return 0;
}