JDOJ-2184: 文艺平衡树

Description

依靠大爷的代码爽爽的A了一道splay的题。（其实很崩溃233）

在节点上加标记，然后下传就好了（说的像是很简单的样子）实际上指针版好难写的+好难理解的+好难想的。

woc 格式还要求没有结尾空格，导致我多开了一个数组

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int k1,k2;
int cnt,a[100010];
struct node
{
    int val,size;bool tur;
    node *fa,*ls,*rs;//结构体指针
    node();//结构体初始化函数
    void push_down();//结构体函数
    void push_up();
    void reverse();
}*null=new node(),*root;//null为一个指针，下面将所有的空指针（fa,ls,rs）都指向它
int n,m;
node :: node()
{
    fa=ls=rs=null;
    tur=false;val=-1;
    size=null?1:0;//null?是在null为空时size为0，非空时为1。
    //（也就是说只有null的size为0）%%%POPOQQQ 姐姐的高级写法
}
void node :: reverse()//区间反转
{
    swap(ls,rs);
    tur^=1;
}
void node :: push_down()//下传标记
{
    if(tur)
    {
        ls->reverse();
        rs->reverse();
        tur=0;
    }
}
void node :: push_up()//由于zig+zag，所以要更新size值
{
    size=ls->size+rs->size+1;
}
node* build(int l,int r)//建树
{
    int mid=(l+r)>>1;
    if(l>r) return null;//将所有的边界都指向null
    node *re=new node();//开一个新的结构体指针
    re->ls=build(l,mid-1);
    re->rs=build(mid+1,r);
    re->val=mid;
    re->ls->fa=re;
    re->rs->fa=re;
    return re->push_up(),re;//计算size
}
void initialize()//初始化
{
    root=new node();
    root->rs=new node();
    root->rs->ls=build(1,n);//在根与根的rs之间建树
    root->rs->ls->fa=root->rs;
    root->rs->fa=root;
    root->rs->push_up();
    root->push_up();
}

void zig(node *x) //超多小细节的右旋
{  
    node *y=x->fa; 
    y->ls=x->rs;  
    x->rs->fa=y;  
    x->rs=y;  
    x->fa=y->fa;  
    if(y==y->fa->ls)  
        y->fa->ls=x;  
    else if(y==y->fa->rs)  
        y->fa->rs=x;  
    y->fa=x; 
    y->push_up();//注意顺序
    x->push_up();
    if(y==root)  
        root=x;  
}  
void zag(node *x)  //左旋
{  
    node *y=x->fa;
    y->rs=x->ls;  
    x->ls->fa=y;  
    x->ls=y;  
    x->fa=y->fa;  
    if(y==y->fa->ls)  
        y->fa->ls=x;  
    else if(y==y->fa->rs)  
        y->fa->rs=x;  
    y->fa=x; 
    y->push_up();//
    x->push_up();
    if(y==root)
        root=x;  
} 
void splay(node *x,node *tar)
{
    while(1)//将x旋转直到fa为tar
    {
        node *y=x->fa,*z=y->fa;
        if(y==tar) break;
        if(z==tar)
        {
            if(x==y->ls) zig(x);
            else zag(x);
            break;
        }
        if(x==y->ls)
        {
            if(y==z->ls) zig(y);
            zig(x);
        }
        else
        {
            if(y==z->rs) zag(y);
            zag(x);
        }
    }
}
void find(node *x,int y,node *z)
{
    while(1)//通过size找到x
    {
        int temp=x->ls->size;
        x->push_down();
        if(y<=temp) x=x->ls;
        else
        {
            y-=temp;
            if(y==1) break;
            y--;
            x=x->rs;
        }
    }
    splay(x,z);//play！！！
}
void dfs(node *x)//中序遍历
{
    if(x==null) return ;
    x->push_down();//下传标记
    dfs(x->ls);
    a[++cnt]=x->val;
    dfs(x->rs);
}
int main()
{
    scanf("%d%d",&n,&m);
    initialize();//
    while(m--)
    {
        scanf("%d%d",&k1,&k2);
        find(root,k1,null);//因为根的fa为null，并且splay是当x的fa满足时退出，所以这样写。
        /*由于find()里是靠size也就是排名找到位置的，
        并且build时是开区间，
        所以将起点的上一名提到根，终点下一名提到跟的rs
        */
        find(root,k2+2,root);//将终点提升直到fa为root
        root->rs->ls->reverse();//标记
    }
    find(root,1,null);//将整个区间提到上面
    find(root,n+2,root);
    dfs(root->rs->ls);
    for(int i=1;i<n;i++) printf("%d ",a[i]);
        printf("%d",a[n]);
    return 0;
}