洛谷 P3391 【模板】文艺平衡树/BZOJ 3223 文艺平衡树 题解

洛谷 P3391 【模板】文艺平衡树/BZOJ 3223 文艺平衡树 题解

2020-2-6 xiaoh

题意

给定一个有$n$个元素的序列($1\leq n\leq 10^5$)，初始情况下第$i$位上的数为$i$。接下来给定$m$个操作($1\leq m \leq 10^5$)，每次操作给定一个区间 $[l,r]$，要求翻转这个区间。输出操作完的序列

题解

正解是$Splay$的，不过这道题我们也可以使用$fhq-Treap$来做。首先先建立一个以下标为键值的$fhq-Treap$，接下来对于每一个翻转操作 $[l,r]$,我们将整棵树$split$成$3$部分：$[1,l-1],[l,r],[r+1,n]$，然后将中间的根打上$tag$，再merge回去。后面的操作中，如果要对某个节点的儿子进行递归，那么就将这个$tag$ $pushdown$，并交换其左右儿子即可。注意由于交换后整棵树已经不满足$BST$的性质，因此不能使用权值分裂，注意到整棵树的中序遍历即为原序列，因此我们使用排名分裂即可。时间复杂度$O(n+mlogn)$。代码与$fhq-Treap$类似，我在代码里就不赘述了，只在需要修改的地方标记。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return;
}
template<typename T>
inline void write(T x)
{
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}
const int MAXN=100010;
int n,m;
int tot;
int rt;
struct node{
    int l,r;
    int val,dat;
    int sz,tag;
}f[MAXN];
inline int New(int val)
{
    ++tot;
    f[tot].val=val,f[tot].dat=rand();
    f[tot].sz=1;
    return tot;
}
inline void update(int p)
{
    f[p].sz=f[f[p].l].sz+f[f[p].r].sz+1;
}
inline void pushdown(int p)//将标记下传
{
    if(!f[p].tag) return;
    swap(f[p].l,f[p].r);//交换子树
    if(f[p].l) f[f[p].l].tag^=1;//下传给儿子
    if(f[p].r) f[f[p].r].tag^=1;//由于儿子也可能有标记，因此只能^1不能=1
    f[p].tag=0;//清空标记
}
void split(int p,int k,int &x,int &y)
{
    if(p==0)
    {
        x=y=0;
        return;
    }
    pushdown(p);//调用前pushdown
    if(k>f[f[p].l].sz)
    {
        x=p;
        split(f[p].r,k-f[f[p].l].sz-1,f[p].r,y);
    }
    else
    {
        y=p;
        split(f[p].l,k,x,f[p].l);
    }
    update(p);
}
int merge(int a,int b)
{
    if(!a||!b) return a+b;
    if(f[a].dat<=f[b].dat)
    {
        pushdown(a);//调用前pushdown
        f[a].r=merge(f[a].r,b);
        update(a);
        return a;
    }
    else
    {
        pushdown(b);//调用前pushdown
        f[b].l=merge(a,f[b].l);
        update(b);
        return b;
    }
}
inline void insert(int val)
{
    int x,y;
    split(rt,val,x,y);
    rt=merge(merge(x,New(val)),y);
    return;
}
inline void reverse(int l,int r)//处理翻转操作
{
    int x,y,z;
    split(rt,l-1,x,y);//将整棵树分成三部分
    split(y,r-l+1,y,z);
    f[y].tag^=1;//打标记
    rt=merge(merge(x,y),z);//再merge回去
}
void dfs(int p)//中序遍历整棵树并输出答案
{
    if(!p) return;
    pushdown(p);
    dfs(f[p].l);
    write(f[p].val),putchar(' ');
    dfs(f[p].r);
}
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++) insert(i);
    for(int i=1;i<=m;i++)
    {
        int l,r;
        read(l),read(r);
        reverse(l,r);
    }
    dfs(rt),putchar('\n');
}