UVA 11922 伸展树Splay 第一题

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 150010
using namespace std;
struct Node
{
  Node *ch[2],*pre;
  int val,size;
  bool rev;
  void update()
  {
      size=ch[0]->size+ch[1]->size+1;
  }
  void pushdown();
}Tnull,*null=&Tnull;//这里要把null设置为指针，由于下面基本上用的指针，有大量判断是否相等，必须统一类型。
void Node::pushdown()//该函数涉及null，不能写在结构体里，否则被认为null未被定义，只能用写在外面这样的方式来实现
{
      if (rev){
        swap(ch[0],ch[1]);
        for (int i=0;i<2;i++)
            if (ch[i]!=null) ch[i]->rev=!ch[i]->rev;
        rev=0;
      }
}
Node nodePool[N];
Node *root,*cur;
int n,m;
Node * newNode(int v,Node* f) //从点池中生成新的点
{
    cur->ch[0]=cur->ch[1]=null;
    cur->size=0;
    cur->val=v;
    cur->rev=0;
    cur->pre=f;
    return cur++;
}
Node*build(int l,int r,Node* f)//建树操作。
{
    if (l>r) return null;
    int mid=(l+r)>>1;
    //printf("%d %d\n",l,r);
    Node* temp=newNode(mid,f);
    temp->ch[0]=build(l,mid-1,temp);
    temp->ch[1]=build(mid+1,r,temp);
    temp->update();
    return temp;

}
void rotate(Node* x,int c) //旋转操作，分情况讨论下就行
{
    Node* y=x->pre;
    y->pushdown();
    x->pushdown();
   // puts("judge1");
    y->ch[!c]=x->ch[c];
    if (x->ch[c]!=null)
        x->ch[c]->pre=y;
    x->pre=y->pre;
   // puts("judge2");
    if (y->pre!=null){
       // puts("deep1");
        //if (y->pre==null) puts("Yes");
        //printf("%d\n",y->pre->size);
        if (y->pre->ch[0]==y){
            //puts("deep2");

            y->pre->ch[0]=x;
          //  puts("deep3");
        }
        else{
           // puts("deep4");
            y->pre->ch[1]=x;
           // puts("deep5");
        }
    }
   // puts("judge3");
    x->ch[c]=y;
    y->pre=x;
    y->update();
    x->update();
    if (y==root)
        root=x;
    //puts("is there?");
}
void Splay(Node* x,Node* f)//Splay过程说白了就是把x节点旋转到f下面，分情况讨论一下就可以
{
    x->pushdown();
    while (x->pre!=f)
    {
        //puts("Why?");
        if (x->pre->pre==f)
        {
            if (x->pre->ch[0]==x)
                rotate(x,1);
            else
                rotate(x,0);
           // puts("pass1");
        }
        else
        {
            //puts("pass2");
            Node *y=x->pre;
            Node *z=y->pre;
            if (z->ch[0]==y)
            {
               // puts("pass3");
                if (y->ch[0]==x)
                    rotate(y,1),rotate(x,1);
                else
                    rotate(x,0),rotate(x,1);
               // puts("pass4");
            }
            else
            {
               // puts("pass5");
                //rotate(y,1);
                if (y->ch[0]==x){
                   // puts("pass6");
                    rotate(x,1);
                    rotate(x,0);
                    //puts("pass7");
                }
                else
                {
                   // puts("pass8");
                    rotate(y,0),rotate(x,0);
                }
               // puts("pass10");
            }
            //puts("pass7");
        }
       // puts("isblock?");
    }
    x->update();
}
void select(int k,Node* f) //把第k个节点旋转到f的下面
{
    int tmp;
    Node* x=root;
    //x->pushdown();
    k++; //因为建树的时候插入了0点作为缓冲点，因此实际的点要++以消除该点的影响。
    for (;;){
     x->pushdown();
     tmp=x->ch[0]->size;
     if (k==tmp+1) break;
     if (k<=tmp)
            x=x->ch[0];
     else{
        k-=tmp+1;
        x=x->ch[1];
     }
    }
    //puts("Test");
    Splay(x,f);
   // puts("t");
}
Node* get(int l,int r)
{
    select(l-1,null);
    //puts("pass");
    select(r+1,root);
   // puts("pass");
    return root->ch[1]->ch[0];
}
void reverses(int a,int b) //翻转操作
{
    Node* o=get(a,b);
    //puts("Pass");
    o->rev=!o->rev;
    Splay(o,null);

}
void split(int l,int r,Node* &s)//切除翻转序列，并把切除的序列用s保存起来
{
    Node*temp=get(l,r);
    root->ch[1]->ch[0]=null;
    root->ch[1]->update();
    root->update();
    s=temp;
}
void cut(int l,int r) //把切除的序列接到序列末端，只需把序列的最右边点移到根节点，再设置它的右孩子为刚刚切除的序列即可
{
    Node *tmp;
    split(l,r,tmp);
    select(root->size-1,null);//把自己手动设置的第n+1点移植到顶点，这样做的原因是防止他干扰，不移它的话，最右点就不是第n点，而是n+1点了
    select(root->size-2,root);
    root->ch[0]->ch[1]=tmp;
    tmp->pre=root->ch[0];
    root->ch[0]->update();
    root->update();
}
void init(int num)
{
    cur=nodePool;
    root=null;
    root=newNode(0,null);
    root->ch[1]=newNode(num+1,root);//设置两个缓冲点，我刚刚还在犹豫n+1点是否需要，经实测确实需要，因为程序中随时要探测自己的子孩子，如果不设置，可能会溢出
    root->ch[1]->ch[0]=build(1,num,root->ch[1]);
    root->update();//
}
void output()
{
    for (int i=1;i<=n;i++)
    {
        select(i,null); //输出某点即把该点旋转到根节点再输出
        printf("%d\n",root->val);
    }
}
int main()
{
    int a,b;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        init(n);
        //output();
        while (m--)
        {
            scanf("%d%d",&a,&b);
            if (a>b) swap(a,b);
            reverses(a,b);
            cut(a,b);
        }
        output();
    }
}