题目是中文的我就不是说明了，比赛的时候看过题目后队友说是splay来做，细想来省赛不会出这么坑的题目吧。
于是比赛还有一个小时左右把该做的都做完了以后，我们队三个人都来思考这个题目了。不过还好很快我们就跳过了这个splay的坑。
因为这个题目根本不是spaly，直接用数组模拟链表就行了，所有的操作都可以再O(1)的时间复杂度以内搞定。
可以这样做，首先对于每一个数，我们都可以视为一个节点，然后一条链的话就相当于是指针操作了，每个节点都设置两个指针——前驱和后继。
设置后继节点是为了应对4操作，因为全部取反只要交换后继和前驱就可以了（其实不用交换也行，只要记录总共要交换多少次就行了，因为换两次就换回来了哦）
对于1、2、3就是简单的链表操作了，不过注意3操作有一个坑，就是x和y可能是相邻的两个节点哦，特别注意了，这里有点坑的。
不过说了，上代码，这个题目时间虽然是O(n)，但是时间还不算宽哦，所以写的时候还是注意一下比较好。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #define maxn 1001000 5 #define ll long long 6 using namespace std; 7 8 int next[maxn],pre[maxn],n,m,k,tim; 9 int *tep,*tep2; 10 11 void init_next_pre() 12 { 13 for (int i=1; i<=n; i++) next[i]=i+1,pre[i]=i-1; 14 next[n]=0; 15 } 16 17 void dele(int x) 18 { 19 int k1=pre[x],k2=next[x]; 20 next[k1]=k2,pre[k2]=k1; 21 } 22 23 void insert(int k1,int mid,int k2) 24 { 25 next[k1]=mid,next[mid]=k2; 26 pre[k2]=mid,pre[mid]=k1; 27 } 28 29 void SWAP(int x,int y) 30 { 31 int k1=pre[x],k2=next[x],k3=pre[y],k4=next[y]; 32 if (k2==y)//考虑xy相邻的情况 33 { 34 next[k1]=y,next[y]=x,next[x]=k4; 35 pre[k4]=x,pre[x]=y,pre[y]=k1; 36 } 37 else if (k4==x)//考虑xy相邻的情况 38 { 39 next[k3]=x,next[x]=y,next[y]=k2; 40 pre[k2]=y,pre[y]=x,pre[x]=k3; 41 } 42 else 43 { 44 next[k1]=y,next[y]=k2,pre[y]=k1,pre[k2]=y; 45 next[k3]=x,next[x]=k4,pre[x]=k3,pre[k4]=x; 46 } 47 } 48 49 int main() 50 { 51 int cod,x,y,cas=0; 52 while (cin>>n>>m) 53 { 54 tim=0; 55 init_next_pre(); 56 while (m--) 57 { 58 cin>>cod; 59 if (cod==4) tim++;//这里只要记录首位交换了多少次哦 60 else 61 { 62 cin>>x>>y; 63 if (cod<3 && tim&1) cod=3-cod;//如果交换了奇数次，那么本来应该插在前面就相当于是现在应该插在后面，T_T不好怎么表达，自己理解一下就懂了。 64 if (cod==1) 65 { 66 dele(x); 67 k=pre[y]; 68 insert(k,x,y); 69 } 70 else if (cod==2) 71 { 72 dele(x); 73 k=next[y]; 74 insert(y,x,k); 75 } 76 else if (cod==3) SWAP(x,y); 77 } 78 } 79 if (tim&1) tep=pre,tep2=next; else tep=next,tep2=pre; 80 for (int i=1; i<=n; i++) 81 { 82 if (tep2[i]==0) 83 { 84 ll ans=0; 85 for (int k=1; i; i=tep[i],k++) if (k&1) ans+=i; 86 cout<<"Case "<<++cas<<": "<<ans<<endl; 87 break; 88 } 89 } 90 } 91 return 0; 92 }