题目：
题意：
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" align="middle" alt="">
分析：数组模拟指针,每一个节点有两个指针(前驱和后继),每一个操作仅仅需改变相关前驱指针和后继指针的值。
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <time.h>
using namespace std;
const int maxn = 1e5+6;
int *Next,*Per,N,M; void Init()
{
for(int i=0;i<=N+1;i++)
{
Next[i]=i+1;
Per[i]=i-1;
}
}
inline void Link1(int x,int y) //put x on the left of y
{
Next[Per[x]]=Next[x];
Per[Next[x]]=Per[x];
Next[x]=y;
Per[x]=Per[y];
Next[Per[y]]=x;
Per[y]=x;
}
inline void Link2(int x,int y) //put x on the right of y
{
Next[Per[x]]=Next[x];
Per[Next[x]]=Per[x];
Next[x]=Next[y];
Per[x]=y;
Per[Next[y]]=x;
Next[y]=x;
}
inline void Link3(int x,int y) //swap a and b
{
if(x==Per[y])
{
Next[Per[x]]=y;
Per[Next[y]]=x;
Per[y]=Per[x];
Next[x]=Next[y];
Next[y]=x;
Per[x]=y;
}
else if(x==Next[y])
{
Next[Per[y]]=x;
Per[Next[x]]=y;
Next[y]=Next[x];
Per[x]=Per[y];
Next[x]=y;
Per[y]=x;
}
else
{
Next[Per[x]]=y;
Next[Per[y]]=x;
int XPE=Per[x],XNE=Next[x],YPE=Per[y],YNE=Next[y];
Per[y]=XPE;
Per[x]=YPE;
Next[x]=YNE;
Next[y]=XNE;
Per[XNE]=y;
Per[YNE]=x;
}
} int main()
{
Next=(int *)malloc(sizeof(int)*maxn);
Per=(int *)malloc(sizeof(int)*maxn);
int i,j,ty,x,y,cnt,tp,ncase=1;
while(scanf("%d%d",&N,&M)!=EOF)
{
Init();
cnt=0;
for(i=1;i<=M;i++)
{
scanf("%d",&tp);
if(tp==1)
{
scanf("%d%d",&x,&y);
if(x==Per[y])
continue ;
Link1(x,y);
}
else if(tp==2)
{
scanf("%d%d",&x,&y);
if(x==Next[y])
continue ;
Link2(x,y);
}
else if(tp==3)
{
scanf("%d%d",&x,&y);
Link3(x,y);
}
else
{
cnt++;
swap(Next,Per);
}
}
long long ans=0;
if(cnt&1)
for(i=Next[N+1];i<=N && i>=1;i=Next[Next[i]])
ans+=i;
else
for(i=Next[0];i<=N && i>=1;i=Next[Next[i]])
ans+=i;
printf("Case %d: %lld\n",ncase++,ans);
}
return 0;
}