思路

splay确实有点绕
还是fhq-treap牛逼啊，构造完美二叉树(他们说笛卡尔树)，就不用rand的，直接计算就好
时间也不慢

代码

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=1e5+7;
const int inf=0x3f3f3f3f;
typedef long long ll;
int read() {
    int x=0,f=1;
    char s=getchar();
    for(; s>'9'||s<'0'; s=getchar()) if(s=='-') f=-1;
    for(; s>='0'&&s<='9'; s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,rt;
int ch[maxn][2],tag[maxn],val[maxn],size[maxn],pri[maxn],cnt;
void pushup(int a) {
    size[a]=size[ch[a][0]]+size[ch[a][1]]+1;
}
void pushdown(int a) {
    if(!tag[a]) return;
    tag[ch[a][0]]^=1;
    tag[ch[a][1]]^=1;
    swap(ch[a][0],ch[a][1]);
    tag[a]=0;
}
int merge(int x,int y) {
    if(!x||!y) return x+y;
    pushdown(x);
    pushdown(y);
    if(pri[x]<pri[y]) {
        ch[x][1]=merge(ch[x][1],y);
        pushup(x);
        return x;
    } else {
        ch[y][0]=merge(x,ch[y][0]);
        pushup(y);
        return y;
    }
}
void split(int now,int k,int &x,int &y) {
    if(!now) x=y=0;
    else {
        pushdown(now);
        if(size[ch[now][0]]+1<=k) x=now,split(ch[now][1],k-size[ch[now][0]]-1,ch[x][1],y);
        else y=now,split(ch[now][0],k,x,ch[y][0]);
        pushup(now);
    }
}
int build(int l,int r) {
    if(l>r) return 0;
    int mid=(l+r)>>1,p=++cnt;
    val[p]=mid;
    size[p]=1;
    pri[p]=cnt;
    ch[p][0]=build(l,mid-1);
    ch[p][1]=build(mid+1,r);
    pushup(p);
    return p;
}
void dfs(int now) {
    pushdown(now);
    if(!now) return;
    dfs(ch[now][0]);
    cout<<val[now]<<" ";
    dfs(ch[now][1]);
} 
int main() {
    n=read(),m=read();
    rt=build(1,n);
    int x,y,z;
    FOR(i,1,m) {
        int a=read(),b=read();
        split(rt,a-1,x,y);
        split(y,b-a+1,y,z);
        tag[y]^=1;
        rt=merge(merge(x,y),z);
    }
    dfs(rt);
    return 0;
}