bzoj 3223: Tyvj 1729 文艺平衡树

.

splay裸题
代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct pnt
{
    int c,sz;
    bool rev;
    pnt *f,*s[2];
    pnt(int x,pnt *f):c(x),f(f),rev(0),sz(1)
    {
        s[0]=s[1]=0;
    }
}*root;
void pushdown(pnt *x)
{
    if(x->rev)
    {
        if(x->s[0])
        {
            x->s[0]->rev^=1;
            swap(x->s[0]->s[0],x->s[0]->s[1]);
        }
        if(x->s[1])
        {
            x->s[1]->rev^=1;
            swap(x->s[1]->s[0],x->s[1]->s[1]);
        }
        x->rev=0;
    }
}
void pushup(pnt *x)
{
    x->sz=1;
    if(x->s[0])
    x->sz+=x->s[0]->sz;
    if(x->s[1])
    x->sz+=x->s[1]->sz;
}
void rot(pnt *x)
{
    pnt *f=x->f,*ff=f->f,*R,*r;
    int w=x==f->s[0];
    R=f;r=x->s[w];
    R->s[1-w]=r;
    if(r)
    r->f=R;
    R=ff;r=x;
    if(R)
    R->s[f==ff->s[1]]=r;
    r->f=R;
    R=x;r=f;
    r->f=R;
    R->s[w]=r;
    pushup(f);
    pushup(x);
}
void splay(pnt *x,pnt *rt)
{
    pushdown(x);
    while(x->f!=rt)
    {
        pnt *f=x->f,*ff=f->f;
        if(ff==rt)
        rot(x);
        else if((f==ff->s[0])==(x==f->s[0]))
        {
            rot(f);
            rot(x);
        }
        else
        {
            rot(x);
            rot(x);
        }
    }
    if(rt==0)
    root=x;
}
pnt* add(int x,pnt *f)
{
    pnt *p=new pnt(x,f);
    if(f)
    {
        f->s[1]=p;
        pushup(f);
        splay(f,0);
    }
    else
    root=p;
    return p;
}
pnt* get(int pos)
{
    pnt *now=root;
    while(1)
    {
        pushdown(now);
        int szl=0;
        if(now->s[0])
        szl=now->s[0]->sz;
        if(szl>=pos)
        now=now->s[0];
        else if(pos>szl+1)
        {
            pos=pos-szl-1;
            now=now->s[1];
        }
        else
        return now;
    }
}
void rev(int l,int r)
{
    r+=2;
    pnt *ll=get(l),*rr=get(r);
    // printf("%d %d\n",ll->c,rr->c);
    splay(ll,0);
    splay(rr,ll);
    pnt *hh=rr->s[0];
    hh->rev^=1;
    swap(hh->s[0],hh->s[1]);
    splay(hh,0);
}
void out(pnt *x)
{
    if(!x)
    return;
    pushdown(x);
    out(x->s[0]);
    if(x->c>0&&x->c<=n)
    printf("%d ",x->c);
    out(x->s[1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    pnt *last=0;
    for(int i=0;i<=n+1;i++)
    last=add(i,last);
    for(int i=0;i<m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        rev(l,r);
    }
    out(root);
}