学步园

SPLAY水题。和HDU上那题一样的操作。。。。复习一下SPLAY，，，UVA提交返回结果好慢。。。等了5分多钟啊。。。。在UVA上面Verdict里是空着的。。。不知道为什么。但在虚拟OJ上面提交过了，返回结果巨慢。。一直processing太奇怪了

题目地址：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3073

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>

using namespace std;

#define MAXN 250000

int next[MAXN];
struct nodes
{
    int ch[2],f;
    int key,size,w,col;
}node[MAXN];

void init()
{
    for(int i=0;i<MAXN-10;i++)
        next[i]=i+1;
}

int newnode(int key)
{
    int p=next[0];
    next[0]=next[p];
    node[p].key=key;
    node[p].w=node[p].size=1;
    node[p].col=0;
    node[p].ch[0]=node[p].ch[1]=node[p].f=0;
    return p;
}

void delnode(int p)
{
    next[p]=next[0];
    next[0]=p;
}

struct spt
{
    int root;

    void clear()
    {
        root=0;
    }
    void rotate(int x,int c)
    {
        int y=node[x].f;
        push_down(y);push_down(x);
        node[y].ch[!c]=node[x].ch[c];
        if(node[x].ch[c])
                node[node[x].ch[c]].f=y;
        node[x].f=node[y].f;
        if(node[y].f)
        {
            if(node[node[y].f].ch[0]==y)
                node[node[y].f].ch[0]=x;
            else
                node[node[y].f].ch[1]=x;
        }
        node[x].ch[c]=y;
        node[y].f=x;
        push_up(y);
        if(y==root) root=x;
    }
    void splay(int x,int f)
    {
        push_down(x);
        for(;node[x].f!=f;)
        {
            push_down(node[node[x].f].f);
            push_down(node[x].f);
            push_down(x);
            if(node[node[x].f].f==f)
            {
                if(node[node[x].f].ch[0]==x)
                    rotate(x,1);
                else
                    rotate(x,0);
            }
            else
            {
                int y=node[x].f;
                int z=node[y].f;
                if(node[z].ch[0]==y)
                {
                    if(node[y].ch[0]==x)
                        rotate(y,1),rotate(x,1);
                    else
                        rotate(x,0),rotate(x,1);
                }
                else
                {
                    if(node[y].ch[1]==x)
                        rotate(y,0),rotate(x,0);
                    else
                        rotate(x,1),rotate(x,0);
                }
            }
        }
        push_up(x);
        if(!f) root=x;
    }
    void split(int l,int r,int &s2)
    {
        select(l,0);
        select(r+2,root);
        int tmp=node[node[root].ch[1]].ch[0];
        node[node[root].ch[1]].ch[0]=0;
        push_up(node[root].ch[1]);
        push_up(root);
        s2=tmp;
    }
    void reverse(int l,int r)
    {
        select(l,0);
        select(r+2,root);
        node[node[node[root].ch[1]].ch[0]].col^=1;
    }
    int select(int k,int rt)
    {
        int tmp,t=root;
        for(;;)
        {
            push_down(t);
            int l=node[node[t].ch[0]].size;
            if(k>l && k<=l+node[t].w) break;
            if(k<=l)
                t=node[t].ch[0];
            else
                k-=(l+node[t].w),t=node[t].ch[1];
        }
        splay(t,rt);
        return t;
    }

    int getmin(int p)
    {
        push_down(p);
        while(node[p].ch[0])
        {
            p=node[p].ch[0];
            push_down(p);
        }
        return p;
    }

    int getmaxn(int p)
    {
        push_down(p);
        while(node[p].ch[1])
        {
            p=node[p].ch[1];
            push_down(p);
        }
        return p;
    }

    void push_down(int rt)
    {
        if(rt && node[rt].col)
        {
            swap(node[rt].ch[0],node[rt].ch[1]);
            int l=node[rt].ch[0];
            int r=node[rt].ch[1];
            node[l].col^=1;
            node[r].col^=1;
            node[rt].col=0;
        }
    }


    void push_up(int rt)
    {
        if(!rt)return;
        int l=node[rt].ch[0];
        int r=node[rt].ch[1];
        int ret=node[rt].w;
        if(l) ret+=node[l].size;
        if(r) ret+=node[r].size;
        node[rt].size=ret;
    }
     void del(int p)
    {
        if(!p) return;
        del(node[p].ch[0]);
        del(node[p].ch[1]);
        delnode(p);
    }

    int build(int l,int r,int f)
    {

        if(l>r) return 0;
        int m=(l+r)>>1;
        int p=newnode(m);
        node[p].f=f;
        node[p].ch[0]=build(l,m-1,p);
        node[p].ch[1]=build(m+1,r,p);
        push_up(p);
        return p;
    }

    void cut(int a,int b,int c)
    {
        spt tmp;
        split(a,b,tmp.root);
        select(c+1,0);
        c=getmin(node[root].ch[1]);
        splay(c,root);
        node[node[root].ch[1]].ch[0]=tmp.root;
        node[tmp.root].f=c;
        push_up(node[root].ch[1]);
        push_up(root);
    }
};
spt s1;
int n,m;

void out(int p)
{
    if(!p)
        return;
    else
    {
        s1.push_down(p);
        out(node[p].ch[0]);
        if(node[p].key!=n+1 && node[p].key!=0)printf("%d\n",node[p].key);
        out(node[p].ch[1]);
    }
}

void prepare()
{
    s1.clear();
    s1.root=newnode(0);
    node[s1.root].ch[1]=newnode(n+1);
    node[node[s1.root].ch[1]].f=s1.root;
    node[node[s1.root].ch[1]].ch[0]=s1.build(1,n,node[s1.root].ch[1]);
    s1.push_up(node[s1.root].ch[1]);
    s1.push_up(s1.root);
}

int main()
{
    init();
    while(~scanf("%d%d",&n,&m))
    {
        prepare();
        int a,b;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            if(b<a) swap(a,b);
            int e=n-(b-a+1);
            s1.reverse(a,b);
            s1.cut(a,b,e);
        }
        out(s1.root);
        s1.del(s1.root);
    }
    return 0;
}