1. 题目

传送门=￣ω￣=

题目大意：

给你一个长度为 $n$的序列，还有 $m$个操作，每次操作给出区间 $[l,r]$，表示将该区间内的数字反转（比如 123 变成 321），求所有操作后的序列。

$n,m<=100000$

2. 题解

裸的 splay 区间操作（反转），拿来练手，毕竟很久没打 splay 了。

splay 的区间操作的话，比如操作 $[l,r]$，只要把 $l-1$所对应的节点 splay 到根，然后再把 $r+1$对应的节点 splay 到根的右儿子，那么区间 $[l,r]$所对应的所有节点就都在 $r+1$的左儿子为根的子树里了，给 $r+1$的左儿子打上标记即可。

由于 $l-1$和 $r+1$可能为 $0$或 $n+1$，所以我们加入两个没用的节点放在 $0$和 $n+1$这两个位置，输出答案的时候注意要判断不为这两个节点再输出。

代码：

#include <bits/stdc++.h>
#define NS (100005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,data[NS],sz,root;
struct N{int s[2],f,d,m,sz;}e[NS];
void pup(int a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+1;}
void pdown(int a)
{
    if(!e[a].m)return;
    e[e[a].s[0]].m^=1,e[e[a].s[1]].m^=1;
    swap(e[a].s[0],e[a].s[1]),e[a].m=0;
}
int build(int fa,int l,int r)
{
    if(l>r)return 0;
    int mid=(l+r)>>1,pos=++sz;
    e[pos].d=data[mid],e[pos].f=fa;
    e[pos].s[0]=build(pos,l,mid-1);
    e[pos].s[1]=build(pos,mid+1,r);
    pup(pos);
    return pos;
}
int jud(int a){return e[e[a].f].s[1]==a;}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=jud(a),q=jud(f);
    pdown(f),pdown(a);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(int a,int t)
{
    while(e[a].f!=t)
    {
        if(e[e[a].f].f!=t)
        {
            if(jud(a)^jud(e[a].f))rot(a);
            else rot(e[a].f);
        }
        rot(a);
    }
    if(!t)root=a;
}
int find_by_order(int x)
{
    int a=root;
    while(a)
    {
        pdown(a);
        if(x<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            x-=e[e[a].s[0]].sz+1;
            if(!x)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
void pans(int a)
{
    pdown(a);
    if(e[a].s[0])pans(e[a].s[0]);
    if(e[a].d!=-1e8&&e[a].d!=1e8)printf("%d ",e[a].d);
    if(e[a].s[1])pans(e[a].s[1]);
}
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)data[i+1]=i;
    data[1]=-1e8,data[n+2]=1e8,root=build(0,1,n+2);
    for(int i=1,l,r;i<=m;i++)
    {
        IN(l),IN(r),l=find_by_order(l),r=find_by_order(r+2);
        splay(l,0),splay(r,l);
        e[e[e[root].s[1]].s[0]].m^=1;
    }
    pans(root);
    return 0;
}