【BZOJ 3223】文艺平衡树 模板题

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
    node();
    node *ch[2],*fa;
    short reversal;
    short pl(){return this==fa->ch[1];}
    int d,sum;
    void push(); void count();
}*null;
int N,M;
node::node(){ch[0]=ch[1]=fa=null;reversal=sum=d=0;}
void node::push(){
    if (this==null) return;
    if (reversal==1){
        reversal=0;
        ch[0]->reversal^=1;
        ch[1]->reversal^=1;
        node *k=ch[0];
        ch[0]=ch[1];
        ch[1]=k;
    }
}
void node::count(){
    sum=ch[0]->sum+ch[1]->sum+1;
}
namespace Splay{
    node *ROOT;
    node *build(int l=1,int r=N){
        if (l>r) return null;
        int mid=(l+r)>>1;
        node *ro=new node;
        ro->d=mid;
        ro->ch[0]=build(l,mid-1);
        ro->ch[1]=build(mid+1,r);
        ro->ch[0]->fa=ro;
        ro->ch[1]->fa=ro;
        ro->count();
        return ro;
    }
    void Build(){
        null=new node;
        *null=node();
        ROOT=build();
        ROOT->count();
    }
    void rotate(node *k){
        node *r=k->fa; if (r==null||k==null) return;
        r->push(); k->push();
        int x=k->pl()^1;
        r->ch[x^1]=k->ch[x];
        r->ch[x^1]->fa=r;
        if (r->fa==null) ROOT=k;
        else r->fa->ch[r->pl()]=k;
        k->fa=r->fa;
        r->fa=k;
        k->ch[x]=r;
        r->count(); k->count();
    }
    void splay(node *r,node *tar=null){
        for (;r->fa!=tar;rotate(r))
         if (r->fa->fa!=tar)rotate(r->pl()==r->fa->pl()?r->fa:r);
        r->push();
    }
    node *kth(int x){
        node *r=ROOT;
        while (r!=null){
            r->push();
            if (r->ch[0]->sum>=x) r=r->ch[0];
            else if (r->ch[0]->sum+1>=x) return r;
            else x-=r->ch[0]->sum+1,r=r->ch[1];
        }return null;
    }
    void rollingover(int ll,int rr){
        node *ln=kth(ll-1),*rn=kth(rr+1),*r;
        if ((ln==null)&&(rn==null)) r=ROOT;
        else if (ln==null){
            splay(rn); r=ROOT->ch[0];
        }else if (rn==null){
            splay(ln); r=ROOT->ch[1];
        }else{
            splay(ln); splay(rn,ROOT);
            r=ROOT->ch[1]->ch[0];
        }r->reversal=r->reversal^1;
    }
    void AC(node *r=ROOT){
        if (r==null) return;
        r->push();
        AC(r->ch[0]);
        printf("%d ",r->d);
        AC(r->ch[1]);
    }
}
int getint()
{
    char c;
    while (!isdigit(c=getchar()));
    int a=c-‘0‘;
    while (isdigit(c=getchar()))
     a=a*10+c-‘0‘;
    return a;
}
int main()
{
    N=getint();M=getint();
    Splay::Build();
    while (M--){
        int l=getint(),r=getint();
        Splay::rollingover(l,r);
    }
    Splay::AC();
    return 0;
}