【题解】Permutation Transformer

题目链接

题意

给定一个 的排列，要求支持区间翻转并加到区间末尾，求所有操作完成后的结果。

思路

文艺平衡树 模板题，不过是加到区间末尾而已。

如果想学习 FHQ-Treap 请右转本人博客 关于 FHQ-Treap 和 Treap 区间操作的简析

简单来说就是不需要旋转维护平衡的平衡树，直接使用分割和合并维护平衡。

在维护二叉搜索树基本性质的基础上，随机一个值 rnd 并维护堆性质。

用途广泛，函数封装代码简单易懂，除了不能写 LCT 以外啥都好。

代码

struct FHQTreap
{
    int l,r,val,rnd,siz,mark;
}tr[N];
int n,cnt=0,rt=0,m;

void update( int x )
{
    tr[x].siz=tr[tr[x].l].siz+tr[tr[x].r].siz+1;
}

int new_node( int val )        //新建节点
{
    cnt++; tr[cnt].siz=1;  tr[cnt].rnd=rand(); tr[cnt].val=val; tr[cnt].mark=0;
    return cnt;
}

void pushdown( int x )        //翻转标记下传
{
    if ( !x || !tr[x].mark ) return;
    tr[x].mark=0; swap( tr[x].l,tr[x].r );
    if ( tr[x].l ) tr[tr[x].l].mark^=1;
    if ( tr[x].r ) tr[tr[x].r].mark^=1;
    update( x );
}

void split( int now,int k,int &x,int &y )        //分割（按照排名分裂）
{
    if ( !now ) { x=y=0; return; }
    pushdown( now );
    if ( k<=tr[tr[now].l].siz ) y=now,split( tr[now].l,k,x,tr[now].l );
    else x=now,split( tr[now].r,k-tr[tr[now].l].siz-1,tr[now].r,y );
    update( now );
}

int merge( int x,int y )        //合并
{
    if ( !x || !y ) return x+y;
    pushdown( x ); pushdown( y );
    if ( tr[x].rnd<tr[y].rnd )
    {
        tr[x].r=merge( tr[x].r,y ); update( x ); return x;
    }
    else
    {
        tr[y].l=merge( x,tr[y].l ); update( y ); return y;
    }
}

void dfs( int x )            //dfs输出
{
    if ( !x ) return; pushdown( x );
    dfs( tr[x].l );
    printf( "%d\n",tr[x].val );
    dfs( tr[x].r );
}

void reverse( int l,int r )
{
    int t1,t2,t3,t4;
    split( rt,r,t1,t2 ); split( t1,l-1,t3,t4 );
    tr[t4].mark^=1; //rt=merge( merge(t3,t4),t2 );
    rt=merge( merge( t3,t2 ),t4 );     //要添加到末尾，所以不一样
}