就文艺平衡树板子

#include<bits/stdc++.h>
using namespace std;
long long f[0x66ccf],ch[0x66ccf][2],size[0x66ccf],flag[0x66ccf],key[0x66ccf],rt,sz;
long long data[0x66ccf];
inline long long read(){
    long long f=1,x=0;
	char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();if(ch=='-')f=-1;};
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();};
    return f*x;
}
inline void update(long long x){
    size[x]=size[ch[x][1]]+size[ch[x][0]]+1;
}
inline long long push(long long x){
    if(x&&flag[x]){
        if(flag[ch[x][0]]!=1) flag[ch[x][0]]=1;
        else flag[ch[x][0]]=0;
        if(flag[ch[x][1]]!=1) flag[ch[x][1]]=1;
        else flag[ch[x][1]]=0;
        swap(ch[x][0],ch[x][1]);
        flag[x]=0;
    }
}
inline long long root(long long x){
    long long k=(ch[f[x]][1]==x),fa=f[x],father=f[fa];
    push(fa);
    push(x);
    ch[fa][k]=ch[x][!k];
    f[ch[x][!k]]=fa;
    ch[x][!k]=fa;
    f[fa]=x;
    f[x]=father;
    if(father) 
        ch[father][ch[father][1]==fa]=x;
    update(fa);
    update(x);
}
inline long long splay(long long x,long long tot){
    for(long long fa;(fa=f[x])!=tot;root(x))
        if(f[fa]!=tot)
            root((ch[f[fa]][1]==fa)==(ch[f[x]][1]==x)?fa:x);
    if(!tot)
        rt=x;
}
inline long long build(long long fa,long long l,long long r){
    if(l<=r) {
        long long mid=(l+r)>>1;
        long long now=++sz;
        key[now]=data[mid];
        f[now]=fa;
        flag[now]=0;
        ch[now][0]=build(now,l,mid-1);
        ch[now][1]=build(now,mid+1,r);
        update(now);
        return now;
    }
    return 0;
}
inline long long find(long long k){
    long long now=rt;
    while(true){
        push(now);
        if (k<=size[ch[now][0]])
            now=ch[now][0];
        else{
            k-=size[ch[now][0]]+1;
            if (!k) return now;
            now=ch[now][1];
        }
    }
}
inline void ask(long long now){
    push(now);
    if(ch[now][0]) 
        ask(ch[now][0]);
    if(key[now]!=-0x66ccff0712 && key[now]!=0x66ccff0712)
        cout<<key[now]<<" ";
    if(ch[now][1]) 
        ask(ch[now][1]);
}
int main(){
    long long n=read(),m=read(),x,y;
    for (long long i=1;i<=n;i++)
        data[i+1]=i;
    data[1]=-0x66ccff0712;
    data[n+2]=0x66ccff0712;
    rt=build(0,1,n+2);
    for(long long i=1;i<=m;i++){
        x=read();
        y=read();
        long long xx=find(x);
        long long yy=find(y+2);
        splay(xx,0);
        splay(yy,xx);
        if(flag[ch[ch[rt][1]][0]]!=1) flag[ch[ch[rt][1]][0]]=1;
        else flag[ch[ch[rt][1]][0]]=0;
    }
    ask(rt);
}