6—5•你有一行盒子，从左到右依次号为1,2,3……,n可以执行以下4种指
p1 X Y表示把盒子X移动到盒子Y的左边（如果X已经在Y的左边则忽略此指令）
p2 X Y表示把盒子X移动到盒子Y的右边（如果X已经在Y的右边则忽略此指令）
p3 X Y表示交换盒子X和Y的位置
p4表示反转整条链
指令保证合法，即X不等于Y。例如：当n=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
•输入包含不超过10组数据，每行数据第一行为盒子个数n和指令条数m（1<=n，m<=100000），以下m行每行包含一条指令。每组数据输出一行，即所有技术位置的盒子编号之和。位置从左到右编号为1~n。
样例输入
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
样例输出：
Case 1:12
Case 2:9
Case 3:2500050000
思路：该题用到了双向链表的思想，即
right[L] = R ; left[R] = L;
①在四个步骤中，4是复杂的，需要用到翻转，如果直接翻转会很耗时，所以采用标记的方法，用inv来标记，执行了几次步骤4，当执行步骤四后，执行步骤一想就是执行步骤二，执行步骤二就是执行步骤一，用下图来解释：
当执行一次步骤4时，inv=1，这个时候这个序列在程序中并没有变，变得只是步骤1.2的替换
②现在来解释步骤1和步骤2，link函数可以直接看为是将里面的参数按顺序排放，如link(x,z)就是把x放在z 的左边，在执行步骤1时要先判断x不在y的左边才要实行，然后执行link(LX, RX), link(LY,X), link(X,Y)
步骤2.3也是用一样的方法
代码为：
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=100000+5;
int n,leftt[maxn],rightt[maxn];//left and right is ambiguous
void link(int L,int R)
{
rightt[L]=R;leftt[R]=L;
}
int main()
{
int m,kase=0;
while(scanf("%d%d",&n,&m)==2)
{
for(int i=1;i<=n;i++)
{
leftt[i]=i-1;
rightt[i]=(i+1)%(n+1);
}
rightt[0]=1;leftt[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&&rightt[Y]==X) swap(X,Y);//!为了转化为同一种情况来处理，x、y只是一个代号，反正结果变得是值
if(op!=3&&inv) op=3-op;
if(op==1&&X==leftt[Y]) continue;
if(op==2&&X==rightt[Y]) continue;
int LX=leftt[X],RX=rightt[X],LY=leftt[Y],RY=rightt[Y];
//下面分类讨论，不要漏掉
if(op==1){
link(LX,RX);link(LY,X);link(X,Y);
}//X的左右连起来，X和Y左，X和Y
else if(op==2){
link(LX,RX);link(Y,X);link(X,RY);
}//X的左右连起来，Y和X，X和Y右 按照链的顺序来写，可能思路更清晰
else if(op==3){
if(rightt[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=rightt[b];//向右推移
if(i%2==1) ans+=b;
}
if(inv&&n%2==0) ans=(long long)n*(n+1)/2-ans;//如果n不是偶数的话，倒一下结果也一样
printf("Case %d: %lld\n",++kase,ans);
}
return 0;
}
