Lvat_s Blog

直接Splay上

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,a[N];
 
struct Node{
int v,rev,siz;
Node *ch[2],*fa;
Node(){}
Node(int vx);
void Pushdown();
void Pushup();
}*root,*Null;
 
Node::Node(int vx){
v=vx;
siz=1;
rev=0;
ch[0]=ch[1]=fa=Null;
}
 
Node *GetNull(){
Node *p=new Node(0);
p->siz=0;
p->ch[0]=p->ch[1]=p->fa=p;
return p;
}
 
void Node::Pushdown(){
if(rev){
    rev=0;
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
}
}
 
void Node::Pushup(){
siz=ch[0]->siz+ch[1]->siz+1;
}
 
void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}
 
void Splay(Node *x,Node *place){
while(x->fa!=place){
    Node *y=x->fa,*z=y->fa;
    if(z==place)Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
        else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
        else {Rotate(y,0);Rotate(x,0);}
    }
}
if(place==Null)root=x;
}
 
Node *Find(Node *splay,int k){
splay->Pushdown();
if(splay->ch[0]->siz+1==k)return splay;
if(splay->ch[0]->siz>=k)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}
 
Node *GetSeq(int l,int r){
Node *Tp1=Find(root,l);
Splay(Tp1,Null);
Node *Tp2=Find(root,r+2);
Splay(Tp2,root);
return Tp2->ch[0];
}
 
Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(a[mid]);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}
 
void PrintTree(Node *rt){
if(rt==Null)return;
rt->Pushdown();
if(rt->ch[0]!=Null)PrintTree(rt->ch[0]);
if(rt->v)printf("%d ",rt->v);
if(rt->ch[1]!=Null)PrintTree(rt->ch[1]);
}
 
void Reverse(int l,int r){
Node *seq=GetSeq(l,r),*fat=seq->fa;
seq->rev^=1;
swap(seq->ch[0],seq->ch[1]);
fat->Pushup();
fat->fa->Pushup();
}
 
int main(){
freopen("3223.in","r",stdin);
freopen("3223.out","w",stdout);
scanf("%d %d",&n,&m);
Null=GetNull();
for(int i=1;i<=n;i++)a[i+1]=i;
root=Build(1,n+2);
for(int i=1;i<=m;i++){
    int l,r;
    scanf("%d %d",&l,&r);
    Reverse(l,r);
}
PrintTree(root);
return 0;
}