# UVa 12657 - Boxes in a Line

---
# 題目大意
1~n照升序排列，接著有m筆操作:
1 x y : 將x插入y的左邊
2 x y : 將x插入y的右邊
3 x y : 將x、y互換
4 將整個序列反轉
最後要求輸出奇數項的總和

---
# 題解
直接模擬雙向list，操作4可以用一個變數來表示，有反轉過就把操作1、2互換。
要注意操作3時x、y相鄰時的相對位置，一開始先統一比較好處理。

---

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define ft first
#define sec second
#define pr pair<ll,ll>
#define ISCC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std; 
int t ,n ,m ,k ,x ,y ,rev ,to[100005][2] ,cas; //0是左，1是右 
void oper(int a ,int b){to[a][1] = b; to[b][0] = a;}
int main()
{
	while(cin >> n >> m)
	{
		rev = 0;
		for(int i=1 ;i<=n ;i++) to[i][0] = i-1 ,to[i][1] = i+1;
		to[n][1] = 0; to[0][1] = 1; to[0][0] = n;
		while(m--)
		{
			cin >> t;
			if(t==4) rev ^= 1;
			else
			{
				cin >> x >> y;
				if(t==3 && to[y][1] == x) swap(x ,y); //統一x在左，y在右 
				if(rev && t!=3) t = (t==1)?2:1;
				if(t == 1 && x == to[y][0]) continue;
                if(t == 2 && x == to[y][1]) continue;
				int rx = to[x][1] ,ry = to[y][1];
				int lx = to[x][0] ,ly = to[y][0];
				if(t==3)
				{
					if(rx == y) //要分有無相連
					{
						oper(lx ,y); oper(y ,x);
						oper(x ,ry);
					} 
					else
					{
						oper(lx ,y); oper(y ,rx);
						oper(ly ,x); oper(x ,ry);
					}
				}
				else if(t==1) 
				{
					oper(lx ,rx);					
					oper(ly ,x); oper(x ,y); 
				}
				else if(t==2)
				{
					oper(lx ,rx);
					oper(x ,ry); oper(y ,x); 
				}
			}
		}
		ll sum = 0 ,now = 0;
		for(int i=1 ;i<=n ;i++) 
		{
			now = to[now][1]; 
			if(i%2) sum += now;
		}
		if(n%2==0 && rev) sum = 1ll*n*(n+1)/2 - sum;
		printf("Case %d: %lld\n",++cas ,sum);
	}	
	return 0;
}