记录编号	432694	评测结果	AAAAAAAAAA
题目名称	2457.[HZOI 2016][Tyvj 1729] 文艺平衡树	最终得分	100
用户昵称	Hzoi_Maple	是否通过	通过
代码语言	C++	运行时间	0.932 s
提交时间	2017-08-03 17:44:01	内存使用	1.74 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m,x,y;
struct Splay{
    int l[N],r[N],k[N],s[N],root;
    bool tag[N];
    int build(int L,int R){
        if(L>R) return 0;
        int mid=(L+R)>>1;
        s[mid]=R-L+1;
        l[mid]=build(L,mid-1);
        r[mid]=build(mid+1,R);
        return mid;
    }
    void pushdown(int x){
        if(tag[x]){
            swap(l[x],r[x]);
            tag[l[x]]^=1;tag[r[x]]^=1;
            tag[x]^=1;
        }
    }
    void update(int x){
        s[x]=s[l[x]]+s[r[x]]+1;
    }
    void l_rot(int &x){
        int y=r[x];
        r[x]=l[y];l[y]=x;
        update(x);update(y);
        x=y;
    }
    void r_rot(int &x){
        int y=l[x];
        l[x]=r[y];r[y]=x;
        update(x);update(y);
        x=y;
    }
    void splay(int &x,int k){
        pushdown(x);
        int i=s[l[x]]+1;
        if(k==i) return;
        if(k<i) splay(l[x],k),r_rot(x);
        else splay(r[x],k-i),l_rot(x);

    }
    void Swap(int L,int R){
        splay(root,L);
        splay(root,R+2);
        tag[r[l[root]]]^=1;
    }
    void search(int x){
        if(!x) return;
        pushdown(x);
        search(l[x]);
        if(k[x]) printf("%d ",k[x]);
        search(r[x]);
    }
}T;
inline int read(){
    int sum=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return sum;
}
int main(){
 	 freopen("sph.in","r",stdin);
 	freopen("sph.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;++i)
        T.k[i+1]=i;
    T.root=T.build(1,n+2);
    for(int i=1;i<=m;++i){
        x=read();y=read();
        T.Swap(x,y);
    }
    T.search(T.root);
    // while(1);
    return 0;
}