1. 题目

传送门=￣ω￣=

2. 题解

Splay 的题解戳我=￣ω￣=

感觉无旋 treap 还是很好理解的。

参考资料：OrzKB 的无旋 treap 博客

代码：

#include <bits/stdc++.h>
#define NS (100005)
#define MKP make_pair
#define FIR first
#define SEC second
using namespace std;
typedef pair<int,int> PII;
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();
}
struct N{int l,r,d,v,rev,sz;}e[NS];
int n,m,root,sz;
void pup(int a){e[a].sz=e[e[a].l].sz+e[e[a].r].sz+1;}
void pdown(int a)
{
    if(!e[a].rev)return;
    int l=e[a].l,r=e[a].r;
    if(l)e[l].rev^=1,swap(e[l].l,e[l].r);
    if(r)e[r].rev^=1,swap(e[r].l,e[r].r);
    e[a].rev=0;
}
int merge(int a,int b)
{
    if(!a)return b;if(!b)return a;
    pdown(a),pdown(b);
    if(e[a].v<e[b].v){e[a].r=merge(e[a].r,b),pup(a);return a;}
    e[b].l=merge(a,e[b].l),pup(b);return b;
}
PII split(int a,int d)
{
    if(!a)return MKP(0,0);
    pdown(a);
    int l=e[a].l,r=e[a].r;
    if(e[l].sz==d){e[a].l=0,pup(a);return MKP(l,a);}
    if(e[l].sz+1==d){e[a].r=0,pup(a);return MKP(a,r);}
    if(e[l].sz>d)
    {
        PII tmp=split(l,d);
        e[a].l=tmp.SEC,pup(a);
        return MKP(tmp.FIR,a);
    }
        PII tmp=split(r,d-e[l].sz-1);
        e[a].r=tmp.FIR,pup(a);
        return MKP(a,tmp.SEC);
}
int build(int l,int r)
{
    if(l==r){sz++,e[sz].d=l,e[sz].v=rand(),e[sz].sz=1;return sz;}
    int mid=(l+r)>>1;
    return merge(build(l,mid),build(mid+1,r));
}
void Print(int a)
{
    if(!a)return;
    pdown(a),Print(e[a].l),printf("%d ",e[a].d),Print(e[a].r);
}
int main()
{
    IN(n),IN(m),srand(n),root=build(1,n);
    for(int i=1,a,b;i<=m;i++)
    {
        IN(a),IN(b);
        PII t2=split(root,b),t1=split(t2.FIR,a-1);
        e[t1.SEC].rev^=1,swap(e[t1.SEC].l,e[t1.SEC].r);
        root=merge(t1.FIR,merge(t1.SEC,t2.SEC));
    }
    Print(root);
    return 0;
}