Problem B

Boxes in a Line

You have n boxes in a line on the table numbered 1~n from left to right. Your task is to simulate 4 kinds of commands:

1 X Y: move box X to the left to Y (ignore this if X is already the left of Y)
2 X Y: move box X to the right to Y (ignore this if X is already the right of Y)
3 X Y: swap box X and Y
4: reverse the whole line.

Commands are guaranteed to be valid, i.e. X will be not equal to Y.

For example, if n=6, after executing 1 1 4, the line becomes 2 3 1 4 5 6. Then after executing 2 3 5, the line becomes 2 1 4 5 3 6. Then after executing 3 1 6, the line becomes 2 6 4 5 3 1. Then after executing 4, then line becomes 1 3 5 4 6 2

Input

There will be at most 10 test cases. Each test case begins with a line containing 2 integers n, m(1<=n, m<=100,000). Each of the following m lines contain a command.

Output

For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n from left to right.

Sample Input

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

Output for the Sample Input

Case 1: 12
Case 2: 9
Case 3: 2500050000

The Ninth Hunan Collegiate Programming Contest (2013)
Problemsetter: Rujia Liu
Special Thanks: Feng Chen, Md. Mahbubul Hasan

#include <iostream>
#include <cstdio>
#include <cstring>

#define toleft p
#define toright p^1

using namespace std;

const int INF=0x3f3f3f3f;
typedef long long int LL;

int lian[200000][2],n,m,p;

void Init()
{
    p=0;
    for(int i=1;i<=n;i++)
    {
        lian[i][0]=i-1;
        lian[i][1]=i+1;
    }
    lian[0][toleft]=INF;
    lian[0][toright]=1;
    lian[n+1][toleft]=n;
    lian[n+1][toright]=INF;
}

void cmdfour()
{
    p=p^1;
}

void cmdone(int x,int y)
{
    int xl=lian[x][toleft],xr=lian[x][toright];
    int yl=lian[y][toleft],yr=lian[y][toright];

    if(xr==y) return;

    lian[xl][toright]=xr;
    lian[xr][toleft]=xl;

    lian[x][toright]=y;
    lian[x][toleft]=yl;

    lian[yl][toright]=x;
    lian[y][toleft]=x;
}

void cmdtwo(int x,int y)
{
    int xl=lian[x][toleft],xr=lian[x][toright];
    int yl=lian[y][toleft],yr=lian[y][toright];

    if(xl==y) return;

    lian[xl][toright]=xr;
    lian[xr][toleft]=xl;

    lian[x][toleft]=y;
    lian[x][toright]=yr;

    lian[y][toright]=x;
    lian[yr][toleft]=x;
}

void cmdthree(int x,int y)
{
    int xl=lian[x][toleft],xr=lian[x][toright];
    int yl=lian[y][toleft],yr=lian[y][toright];

    if(xr!=y&&xl!=y)
    {
        lian[x][toleft]=yl;
        lian[x][toright]=yr;
        lian[yl][toright]=x;
        lian[yr][toleft]=x;

        lian[y][toleft]=xl;
        lian[y][toright]=xr;
        lian[xl][toright]=y;
        lian[xr][toleft]=y;
    }
    else
    {
        if(xr==y)
        {
            lian[x][toright]=yr;
            lian[x][toleft]=y;

            lian[y][toright]=x;
            lian[y][toleft]=xl;

            lian[xl][toright]=y;
            lian[yr][toleft]=x;
        }
        else if(xl==y)
        {
            lian[x][toleft]=yl;
            lian[x][toright]=y;

            lian[y][toleft]=x;
            lian[y][toright]=xr;

            lian[xr][toleft]=y;
            lian[yl][toright]=x;
        }

    }
}

LL getSum()
{
    LL ans=0;
    int cnt=1,pos=0;
    if(n%2==1||p==0)
    {
        if(p) p=0;
        while(true)
        {
            if(cnt&1) ans+=(LL)lian[pos][toright];
            pos=lian[pos][toright];
            cnt++;
            if(cnt>=n+1) break;
        }
    }
    else if(p==1)
    {
        if(p) p=0;
        while(true)
        {
            if(cnt%2==0) ans+=(LL)lian[pos][toright];
            pos=lian[pos][toright];
            cnt++;
            if(cnt>=n+1) break;
        }
    }
    return ans;
}

int main()
{
    int cas=1,cmd,x,y;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        Init();

        while(m--)
        {
            scanf("%d",&cmd);
            if(cmd==1)
            {
                scanf("%d%d",&x,&y);
                cmdone(x,y);
            }
            else if(cmd==2)
            {
                scanf("%d%d",&x,&y);
                cmdtwo(x,y);
            }
            else if(cmd==3)
            {
                scanf("%d%d",&x,&y);
                cmdthree(x,y);
            }
            else if(cmd==4)
            {
                cmdfour();
            }
        }
        LL ans=getSum();
        printf("Case %d: %lld
",cas++,ans);
    }
    return 0;
}