RT

本地测试秒出解，洛谷上TLE

#include<iostream>
#include<cstdio>
#include<algorithm>
#define lc ch[x][0]
#define rc ch[x][1]
#define gt getchar()
#define rg register
using namespace std;
const int N=5e4+5;
int f[N],ch[N][2],lz[N],root,s[N],cnt,val[N],n,m;
inline int in()
{
    int k=0,p=1;
    char ch=gt;
    while((ch>'9'||ch<'0')&&ch!='-')ch=gt;
    if(ch=='-')p=-1,ch=gt;
    while(ch>='0'&&ch<='9')k=(k<<3)+(k<<1)+(ch^48),ch=gt;
    return k*p;
}
inline void clear(int x){ch[x][0]=ch[x][1]=f[x]=lz[x]=0;}
inline int get(int x){return ch[f[x]][1]==x;}
inline void maintain(int x){s[x]=s[lc]+s[rc]+1;}
inline void update(int x)
{
    if(!x)return;
    if(lz[x])
    {
        lz[lc]^=1,lz[rc]^=1,lz[x]^=1;
        swap(lc,rc);
    }
    return;
}
inline void rotate(int x)
{
    update(f[x]);update(x);
    int fa=f[x],gr=f[fa],p=get(x);
    ch[fa][p]=ch[x][p^1];f[ch[fa][p]]=fa;
    ch[x][p^1]=fa;f[fa]=x;f[x]=gr;
    if(gr)
    {
        int d=ch[gr][1]==fa;
        ch[gr][d]=x;
    }
    maintain(fa);maintain(x);
}
inline void splay(int x,int mu)
{
    for(int fa;(fa=f[x])!=mu;rotate(x))
        if(f[fa]!=mu)
            rotate(get(x)==get(fa)?fa:x);
    if(!mu)root=x;maintain(x);
}
int init(int l,int r,int fa)
{
    int x=++cnt,mid=(l+r)>>1;
    f[x]=fa,val[x]=mid;
    if(l<mid)lc=init(l,mid-1,x);
    if(r>mid)rc=init(mid+1,r,x);
    maintain(x);
}
inline int kth(int k,int x)
{
    update(x);
    int d=s[lc];
    if(k==d+1)return x;
    if(k<=d)return kth(k,lc);
    return kth(k-d-1,rc);
}
void print(int x)
{
    if(x)
    {
        update(x);
        print(lc);
        if(val[x]>=1&&val[x]<=n)printf("%d ",val[x]);
        print(rc);
    }
}
int main()
{
    n=in();
    root=init(0,n+1,0);
    m=in();
    while(m--)
    {
        int l=in(),r=in();
        l=kth(l,root);r=kth(r+2,root);
        splay(l,0),splay(r,l);
        lz[ch[r][0]]^=1;
    }
    print(root);
    return 0;
}