UVA 12657 Boxes in a Line 双向链表模拟

说一下题意：
给你一个长度为n，节点值由1到n的链表。
定义四种操作：
1 X Y：把值为X的节点放到值为Y 的节点左边。
2 X Y：把值为Y的节点放到值为X的节点右边。
3 X Y：交换X、Y两个节点
4：翻转整个链表

说一下坑点：
1.初始化链表时用循环写。递归会导致栈溢出。
2.注意细节，首节点和尾节点注意一下。
3.翻转后，其实可以看做还是原来的链表，只是1、2操作功能对调
4.你可以不翻转链表，坑点3提示的操作，最后计算奇数节点值的时候判断一下是从左向右还是反方向就行。

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N=1e5+5;

struct node
{
    int val;
    node *lp,*rp;
}oo[N];

node *pp[N];

node* leftt,*rightt;

///初始化链表
void mark_list(int n)
{
    int i=1;
    while(i<=n)
    {
        pp[i]=&oo[i];
        oo[i].val=i;
        oo[i].lp=&oo[i-1];
        oo[i].rp=&oo[i+1];
        i++;
    }
    oo[1].lp=NULL;
    oo[n].rp=NULL;

    leftt=pp[1];
    rightt=pp[n];
}

void remove_a(node*a)
{
    if(a->lp==NULL)
    {
        (a->rp)->lp=NULL;
        leftt=a->rp;
    }
    else if(a->rp==NULL)
    {
        (a->lp)->rp=NULL;
        rightt=a->lp;
    }
    else
    {
        (a->lp)->rp=a->rp;
        (a->rp)->lp=a->lp;
    }

}

void toleft(node* a,node* b)
{
    remove_a(a);
    if(b->lp!=NULL)
    {
        (b->lp)->rp=a;
        a->lp=(b->lp);
    }
    else
    {
        a->lp=NULL;
    }

    b->lp=a;
    a->rp=b;

    if(leftt==b)    leftt=a;
}

void toright(node* a,node* b)
{
    remove_a(a);
    if(b->rp!=NULL)
    {
        (b->rp)->lp=a;
        a->rp=(b->rp);
    }
    else
    {
        a->rp=NULL;
    }

    b->rp=a;
    a->lp=b;

    if(rightt==b)   rightt=a;
}

void just_swap(node *a,node *b)
{
    int t;

    t=a->val;
    a->val=b->val;
    b->val=t;

    pp[a->val]=a;
    pp[b->val]=b;

}

ll sum(bool flag)
{
    ll ans=0;
    bool mark=true;
    node *p=(flag ? rightt:leftt);
    while(p!=NULL)
    {
        if(mark)
        {
            ans+=p->val;
        }

        p=(flag ? p->lp:p->rp);
        mark=!mark;
    }
    return ans;
}

void putlink()
{
    node *p=leftt;
    while(p!=NULL)
    {
        cout<<(p->val)<<" ";
        p=p->rp;
    }
    cout<<""<<endl;
}

int main()
{
    int n,m,Case=0;

    while(cin>>n>>m)
    {
        mark_list(n);

        bool mark;

        mark=false;


        while(m--)
        {
            int op,x,y;
            cin>>op;
            if(mark)
            {
                if(op==1)   op=2;
                else if(op==2) op=1;
            }
            switch(op)
            {
            case 1:
                cin>>x>>y;
                if(pp[y]->lp!=pp[x]&&n!=1)
                {
                    toleft(pp[x],pp[y]);
                }
                //putlink();
                break;
            case 2:
                cin>>x>>y;
                if(pp[y]->rp!=pp[x]&&n!=1)
                {
                    toright(pp[x],pp[y]);
                }
                //putlink();
                break;
            case 3:
                int x,y;
                cin>>x>>y;
                if(n!=1)
                {
                    just_swap(pp[x],pp[y]);
                }
                //putlink();
                break;
            case 4:
                mark=!mark;
                //putlink();
                break;
            default:
                break;
            }
        }

        cout<<"Case "<<(++Case)<<": "<<sum(mark)<<endl;
    }

    return 0;
}