题解 | #文艺平衡树#

板子题，FHQ-treap秒杀 只要将懒标记定义为翻转所有数即可

#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
const int M=2e5+10;
ll cnt,x,y,z,root;
struct FHQ_Treap
{ll x,ls,rs,sz,lz,key;}s[M];
inline ll NewNode(ll v)
{
    s[++cnt]=(FHQ_Treap){v,0,0,1,0,rand()};
    return cnt;
}
inline void push_up(ll u)
{
    s[u].sz=s[s[u].ls].sz+s[s[u].rs].sz+1;
}
inline void push_down(ll u)
{
    if(!s[u].lz)return;
    swap(s[u].ls,s[u].rs);
    s[s[u].ls].lz^=1;
    s[s[u].rs].lz^=1;
    s[u].lz=0;
}
ll Merge(ll x,ll y)
{
    if(s[x].lz)push_down(x);
    if(s[y].lz)push_down(y);
    if(!x||!y)return x+y;
    if(s[x].key<s[y].key)return s[x].rs=Merge(s[x].rs,y),push_up(x),x;
    else return s[y].ls=Merge(x,s[y].ls),push_up(y),y;
}
void split(ll now,ll size,ll &x,ll &y)
{
    if(!now){x=y=0;return;}
    push_down(now);
    if(s[s[now].ls].sz>=size)y=now,split(s[now].ls,size,x,s[now].ls);
    else x=now,split(s[now].rs,size-s[s[now].ls].sz-1,s[now].rs,y);
    push_up(now);
}
inline void Insert(ll v,ll pos)
{
    split(root,pos-1,x,y);
    root=Merge(Merge(x,NewNode(v)),y);
}
inline void add(ll l,ll r)
{
    split(root,r,x,z);split(x,l-1,x,y);
    s[y].lz^=1;
    root=Merge(Merge(x,y),z);
}
void dfs(ll now)
{
    if(!now)return;
    push_down(now);
    dfs(s[now].ls);
    cout << s[now].x << ' ';
    dfs(s[now].rs);
}
int main()
{
    ll n,m;
    srand(1919810);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i)
    {
        Insert(i,i);
    }
    while(m--)
    {
        ll l,r;
        scanf("%lld%lld",&l,&r);
        add(l,r);
    }
    dfs(root);
}