[UVA] 12657 - Boxes in a Line

題意:
輸入N表示1,2,3...,N個數字連接成一條鏈，
現在有四種操作:
1 x y :將 x 移到 y 左邊

2 x y :將 x 移到 y 右邊

3 x y :將 x 和 y 交換位置

4       :反轉整條鏈

最後輸出鏈上奇數位置的數字總和。

--------------------------------------------------

方法:

直接使用vector模擬操作會超時，

這題要用雙向鏈接串列，

一開始先串接這N個數字，

小技巧:先設置一個head和一個last，但要保證不會使用到這兩個數字

例如題目只會用到1~100000的數字，head就可以設為0，last設為100001

那麼一開始串接起來就變成

0-1-2-3-.....-N-100001

因為任何操作都不會動到head和last，

這樣在輸出時比較方便，

操作4的反轉整條鏈比較麻煩，

直接模擬的話要整條鏈都掃一遍，太費時，

所以可以先用一個記號表示目前這條鏈是否有反轉，

如果沒有反轉:

輸出時從head開始輸出，

如果有反轉:

那麼操作1就變成操作2，

操作2就變成操作1，

輸出時從last輸出，

操作3要注意的是 ! 要額外判斷 x y 是否相鄰 ! 不然會被吃掉

--------------------------------------------------

/* 20150820
 * hanting
 * UVa 12657 - Boxes in a Line
 * C++
 */
#include <iostream>
using namespace std;
const int maxn=100000+5;
int Left[maxn],Right[maxn];
#define head 0
#define last 100003
void Link(int L,int R)
{
    Right[L]=R;
    Left[R]=L;
}
void initial(int N)
{
    Link(head,1);
    for(int i=1;i<N;i++)
    {
        Link(i,i+1);
    }
    Link(N,last);
}
int main()
{
    int boxN,cmdN;
    int caseN=1;
    while(cin>>boxN>>cmdN)
    {
        initial(boxN);//串接N個數字
        bool Reverse=false;
        for(int i=0;i<cmdN;i++)
        {
            int cmd,x,y;
            cin>>cmd;
            if(cmd!=4)
            {
                cin>>x>>y;
            }
            else//反轉整條鏈
            {
                Reverse=!Reverse;
            }
            int Lx=Left[x],Rx=Right[x];
            int Ly=Left[y],Ry=Right[y];
            if(Reverse and cmd<3) cmd=3-cmd;
            switch(cmd)
            {
            case 1://把x移動到y左邊
                if(Ly==x) break;//x已經在y左邊
                Link(Ly,x);
                Link(x,y);
                Link(Lx,Rx);
                break;
            case 2://把x移動到y右邊
                if(Ry==x) break;//x已經在y右邊
                Link(y,x);
                Link(x,Ry);
                Link(Lx,Rx);
                break;
            case 3://x與y的位置交換
                if(Lx==y)//y在x左邊
                {
                    Link(Ly,x);
                    Link(x,y);
                    Link(y,Rx);
                }
                else if(Rx==y)//y在x右邊
                {
                    Link(Lx,y);
                    Link(y,x);
                    Link(x,Ry);
                }
                else
                {
                    Link(Lx,y);
                    Link(y,Rx);
                    Link(Ly,x);
                    Link(x,Ry);
                }
                break;
            }
        }
        cout<<"Case "<<caseN++<<": ";
        long long sum=0;
        if(Reverse)
        {
            for(int i=Left[last] ,j=0; i!=head ; i=Left[i],j++)
            {
                if(!(j&1)) sum+=i;
            }
        }
        else
        {
            for(int i=Right[head],j=0 ; i!=last ; i=Right[i],j++)
            {
                if(!(j&1)) sum+=i;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}