题目：

You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4 kinds of commands: ? 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y ) ? 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y ) ? 3 X Y : swap box X and Y ? 4: reverse the whole line. Commands are guaranteed to be valid, i.e. X will be not equal to Y . For example, if n = 6, after executing 1 1 4, the line becomes 2 3 1 4 5 6. Then after executing 2 3 5, the line becomes 2 1 4 5 3 6. Then after executing 3 1 6, the line becomes 2 6 4 5 3 1. Then after executing 4, then line becomes 1 3 5 4 6 2

Input

There will be at most 10 test cases. Each test case begins with a line containing 2 integers n, m (1 ≤ n, m ≤ 100, 000). Each of the following m lines contain a command.

Output

For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n from left to right.

Sample Input

6 4

1 1 4

2 3 5

3 1 6

4

6 3

1 1 4

2 3 5

3 1 6

100000 1

4

Sample Output

Case 1: 12

Case 2: 9

Case 3: 2500050000

代码：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 100000 + 5;
int n, left[maxn], right[maxn];

inline void link(int L, int R) ///inline将link设置为内嵌函数
{
right[L] = R;
left[R] = L;///把L放到L的右边，把
}

int main()
{
int m, kase = 0;
while(scanf("%d%d", &n, &m) == 2)
{
for(int i = 1; i <= n; i++)
{
left[i] = i-1;
right[i] = i+1;
}
right[0] = 1;
left[0] = n;
int op, X, Y, inv = 0;

while(m--)
{
scanf("%d", &op);
if(op == 4) inv = !inv;
else
{
scanf("%d%d", &X, &Y);
if(op == 3 && right[Y] == X) swap(X, Y);
if(op != 3 && inv) op = 3 - op;
if(op == 1 && X == left[Y]) continue;
if(op == 2 && X == right[Y]) continue;

int LX = left[X], RX = right[X], LY = left[Y], RY = right[Y];
if(op == 1)
{
link(LX, RX); ///将X两边的数相互连接
link(LY, X);///将X连接到Y的左边
link(X, Y);///将X，Y相连
}
else if(op == 2)
{
link(LX, RX);///将X两边的数相互连接
link(Y, X);///将Y，X相连
link(X, RY);///将X与Y的右边相连
}
else if(op == 3)
{
if(right[X] == Y) ///交换X，Y的位置
{
link(LX, Y);
link(Y, X);
link(X, RY);
}
else
{
link(LX, Y);
link(Y, RX);
link(LY, X);
link(X, RY);
}
}
}
}

int b = 0;
long long ans = 0;
for(int i = 1; i <= n; i++)
{
b = right[b];
if(i % 2 == 1) ans += b;
}
if(inv && n % 2 == 0) ans = (long long)n*(n+1)/2 - ans;///如果翻转过，而且数据数量是偶数，那么原先奇数的位置就变成了偶数，所以只需要将总值减去ans中的值即可
printf("Case %d: %lld\n", ++kase, ans);
}
return 0;
}

双向链表