题目

题目链接：https://www.luogu.com.cn/problem/P3391
您需要写一种数据结构（可参考题目标题），来维护一个有序数列。
其中需要提供以下操作：翻转一个区间，例如原有序序列是 \(5\ 4\ 3\ 2\ 1\)，翻转区间是 \([2,4]\) 的话，结果是 \(5\ 2\ 3\ 4\ 1\)。

思路

Splay 模板。总算是会抠 Splay 了。
Treap 采用键值随机化来维护 BST 平衡，而 Splay 则采用旋转来维护 BST 平衡。基本上每进行一次关于 \(x\) 的操作，就把 \(x\) 旋转至树根。
对于区间旋转的操作，我们以下标建立一棵 Splay，对于旋转 \([l,r]\)，我们将 \(l\) 的前驱旋转至树根，\(r\) 的后继旋转至树根的右子节点，那么此时 \(r\) 的后继的左子树即为 \([l,r]\)。
那么就把 \(r\) 后继的左子树的树根打上一个懒惰标记，下次旋转该点时就将该点的左右子树互换，类似线段树的标记下传。
时间复杂度不会证。

代码

这份代码还有很多地方可以简化，但是太懒了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100010,Inf=2e9;
int n,Q,rt;

struct Splay
{
    int tot,val[N],fa[N],son[N][2],cnt[N],size[N];
    bool tag[N];
    
    void pushup(int x)
    {
        size[x]=size[son[x][1]]+size[son[x][0]]+cnt[x];
    }
    
    void pushdown(int x)
    {
        if (tag[x])
        {
            tag[son[x][0]]^=1; tag[son[x][1]]^=1;
            swap(son[x][0],son[x][1]);
            tag[x]=0;
        }
    }
    
    bool pos(int x)
    {
        return x==son[fa[x]][1];
    }
    
    void build()
    {
        tot=2; rt=1; 
        val[1]=-Inf; val[2]=Inf;
        fa[2]=1; son[1][1]=2;
        cnt[1]=cnt[2]=1;
        pushup(2); pushup(1); 
    }
    
    void rotate(int x)
    {
        pushdown(x);
        int y=fa[x],z=fa[y],k=pos(x),c=son[x][k^1];
        fa[c]=y; son[y][k]=c;
        fa[x]=z; son[z][pos(y)]=x;
        fa[y]=x; son[x][k^1]=y;
        pushup(y); pushup(x);
    }
    
    void splay(int x,int f=0)
    {
        while (fa[x]!=f)
        {
            int y=fa[x],z=fa[y];
            if (z!=f)
            {
                if (pos(x)==pos(y)) rotate(y);
                    else rotate(x);
            }
            rotate(x);
        }
        if (!f) rt=x;
    }
    
    void ins(int x)
    {
        int p=rt,f=0;
        while (p && val[p]!=x)
        {
            f=p;
            if (val[p]<x) p=son[p][1];
                else p=son[p][0];
        }
        if (val[p]==x) cnt[p]++;
        else
        {
            p=++tot;
            val[p]=x; cnt[p]=size[p]=1;
            fa[p]=f; son[f][x>val[f]]=p;
        }
        pushup(p); pushup(f);
        splay(p);
    }
    
    int get_val(int k)
    {
        int p=rt;
        while (1)
        {
            pushdown(p);
            if (size[son[p][0]]>=k) p=son[p][0];
            else if (k<=size[son[p][0]]+cnt[p]) break;
            else k-=size[son[p][0]]+cnt[p],p=son[p][1];
        }
        splay(p);
        return p;
    }
    
    void reverse(int l,int r)
    {
        int p=get_val(l),q=get_val(r+2);
        splay(p); 
        splay(q,p);
        tag[son[q][0]]^=1;
    }
}splay;

void dfs(int x)
{
    if (!x) return;
    splay.pushdown(x);
    dfs(splay.son[x][0]);
    if (x>2) printf("%d ",splay.val[x]);
    dfs(splay.son[x][1]);
}

int main()
{
    scanf("%d%d",&n,&Q);
    splay.build();
    for (int i=1;i<=n;i++)
        splay.ins(i);
    while (Q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        splay.reverse(l,r);
    }
    dfs(rt);
    return 0;
}

【洛谷P3391】【模板】文艺平衡树

原文：https://www.cnblogs.com/stoorz/p/12495375.html