题解：P10689 SuperMemo

microchip · 2024-07-19 15:36:07 · 题解

题意翻译：

你需要维护一个序列，支持以下操作：

ADD x y D 将序列中第 x 到 y 个元素加 d .

REVERSE x y 将序列中第 x 到 y 个元素进行区间翻转操作.

REVOLVE x y D 定义右移操作为将某个区间的最后一个元素移动到该区间的最前面，将序列中第 x 到 y 个元素所在的区间进行 d 次右移操作.

INSERT x P 将元素 P 插入到序列中第 x 个元素的后面.

DELETE x 删除序列中第 x 个元素.

MIN x y 求序列中第 x 到 y 个元素的最小值.

Solution：伸展树

众所周知，对于复杂的序列维护问题（如区间翻转），我们常用平衡树来维护.常用的序列平衡树有两种：Splay Tree 和 FHQ Treap.

这里我们使用 Splay 来解决此题.

阅读前请先使用 Splay 完成 普通平衡树 和 文艺平衡树 来熟悉 Splay 的基本操作，以及如何使用 Splay 来处理区间操作，本题解默认您已经了解这些内容.

Step 1：建树

最简单粗暴的办法是以 n \log n 的复杂度依次对每个元素执行插入操作，但我们有更高明的办法：

void build(int l,int r,int &no,int a[]){
    if(l>r)return;
    if(no==0)no=++nth;
    int mid=(l+r)/2;
    Tr[no].val=a[mid];
    Tr[no].min_val=Tr[no].val;
    build(l,mid-1,Tr[no].left,a);
    if(Tr[no].left){
        Tr[Tr[no].left].fa=no;
        Tr[no].min_val=min(Tr[no].min_val,Tr[Tr[no].left].min_val);
    }
    build(mid+1,r,Tr[no].right,a);
    if(Tr[no].right){
        Tr[Tr[no].right].fa=no;
        Tr[no].min_val=min(Tr[no].min_val,Tr[Tr[no].right].min_val);
    }
    update(no);
}

这里是将原有数列直接构造成一个完美的平衡树，每次选取数列的中位数作为根，将左半部分作为左儿子，右半部分作为右儿子，递归建树，这样建树的复杂度是 O(n).

同时我们给每个节点维护了该点代表区间的最小值，用于查询 RMQ.

注意要在序列的头和尾多加一个元素，保证不出现越界问题.

Step 2：查询区间最小值

通过文艺平衡树一题，我们知道 Splay 提取区间 [l,r] 的方式是先将 l-1 旋转至根处，再将 r+1 旋转至根下，这样根节点的右子树的左子树就代表了区间 [l,r].

问题在于在旋转的过程中，被旋转的点所代表的区间会变化，所以在旋转的过程中我们要注意区间最小值的更新.

先考虑左旋，如下图：

橙色是我们要向上旋转的一个节点，我们发现该节点所代表的区间变成了其父节点所代表的区间，而父节点所代表的区间变成了 b 子树和 c 子树的区间外加自己.

于是我们在原有旋转代码之中加上这样一个更新操作即可：

Tr[no].min_val=Tr[tmp].min_val;// tmp 表示 no 的父节点

Tr[tmp].min_val=min(Tr[tmp].val,min(Tr[Tr[tmp].right].min_val,Tr[Tr[no].right].min_val));

右旋操作同理.

这样我们就可以查询任意区间的最小值了.

Step 3：修改操作

插入和删除是平衡树的基操，这里不再赘述.

翻转操作和区间加操作通过延时标记来高效解决，相信过了文艺树的您肯定可以很快写出来.

注意每次旋转操作和查询第 k 个元素时都要将遍历到的点进行标记下传.代码如下：

void tag_pushdown(int no){
    if(Tr[no].tag_rev){//翻转标记
        swap(Tr[no].left,Tr[no].right);
        Tr[Tr[no].left].tag_rev^=1;
        Tr[Tr[no].right].tag_rev^=1;
        Tr[no].tag_rev=0;
    }
    if(Tr[no].tag_add){//加法标记
        Tr[Tr[no].left].val+=Tr[no].tag_add;
        Tr[Tr[no].left].min_val+=Tr[no].tag_add;
        Tr[Tr[no].left].tag_add+=Tr[no].tag_add;
        Tr[Tr[no].right].val+=Tr[no].tag_add;
        Tr[Tr[no].right].min_val+=Tr[no].tag_add;
        Tr[Tr[no].right].tag_add+=Tr[no].tag_add;
        Tr[no].tag_add=0;
    }
}

void range_rev(int l,int r){
    kth_num(r+2);
    int tmp=root;
    kth_num(l);
    splay_under_root(tmp);
    Tr[Tr[Tr[root].right].left].tag_rev^=1;
    tag_pushdown(Tr[Tr[root].right].left);
}
void range_add(int l,int r,int val){
    kth_num(r+2);
    int tmp=root;
    kth_num(l);
    splay_under_root(tmp);
    Tr[Tr[Tr[root].right].left].tag_add+=val;
    Tr[Tr[Tr[root].right].left].min_val+=val;
    Tr[Tr[Tr[root].right].left].val+=val;
}

区间右移操作可以等价于区间移动操作，显然，如果移动的步数等于区间长度，那么就相当于没有操作，所以我们先将 D 对 y-x+1 取模，此时就相当于将区间 [x,y-D] 移动到区间 [y-D+1,y] 的后方.

代码如下：

void range_mov(int l,int r,int stp){
    kth_num(r-stp+2);
    int tmp=root;
    kth_num(l);
    splay_under_root(tmp);
    int Root=Tr[Tr[root].right].left;
    Tr[Tr[root].right].left=0;
    Tr[Tr[root].right].siz-=Tr[Root].siz;
    Tr[root].siz-=Tr[Root].siz;
    kth_num(l+stp+1);
    int tmp2=root;
    kth_num(l+stp);
    splay_under_root(tmp2);
    Tr[Tr[root].right].left=Root;
    Tr[Tr[root].right].siz+=Tr[Root].siz;
    Tr[root].siz+=Tr[Root].siz;
    Tr[Root].fa=Tr[root].right;
}

于是这道题就解决啦.

AC 代码如下，使用 class 封装的伸展树（码风有点抽象，见谅）：

#include<iostream>
using namespace std;

class Splay_Tree{
    private:
        struct node{
            long long val,tag_add,min_val;
            int fa,left,right,siz;
            bool tag_rev;
        }Tr[200050];
        int root,nth,x,k;
    public:
        long long min(long long x,long long y){
            return x<y?x:y;
        }
        bool son(int no){
            return Tr[Tr[no].fa].right==no;
        }
        void update(int no){
            Tr[no].siz=Tr[Tr[no].left].siz+1+Tr[Tr[no].right].siz;
        }
        void tag_pushdown(int no){
            if(Tr[no].tag_rev){
                swap(Tr[no].left,Tr[no].right);
                Tr[Tr[no].left].tag_rev^=1;
                Tr[Tr[no].right].tag_rev^=1;
                Tr[no].tag_rev=0;
            }
            if(Tr[no].tag_add){
                Tr[Tr[no].left].val+=Tr[no].tag_add;
                Tr[Tr[no].left].min_val+=Tr[no].tag_add;
                Tr[Tr[no].left].tag_add+=Tr[no].tag_add;
                Tr[Tr[no].right].val+=Tr[no].tag_add;
                Tr[Tr[no].right].min_val+=Tr[no].tag_add;
                Tr[Tr[no].right].tag_add+=Tr[no].tag_add;
                Tr[no].tag_add=0;
            }
        }
        void rotate(int no){
            if(no==root)return;
            int tmp=Tr[no].fa;
            tag_pushdown(tmp);
            tag_pushdown(no);
            Tr[no].min_val=Tr[tmp].min_val;
            if(son(no)==0){
                Tr[tmp].min_val=min(Tr[tmp].val,min(Tr[Tr[tmp].right].min_val,Tr[Tr[no].right].min_val));
                Tr[tmp].left=Tr[no].right;Tr[Tr[no].right].fa=tmp;Tr[no].right=tmp;
            }else{
                Tr[tmp].min_val=min(Tr[tmp].val,min(Tr[Tr[tmp].left].min_val,Tr[Tr[no].left].min_val));
                Tr[tmp].right=Tr[no].left;Tr[Tr[no].left].fa=tmp;Tr[no].left=tmp;
            }update(tmp);update(no);
            if(tmp==root){
                root=no;
                Tr[no].fa=0;Tr[tmp].fa=no;
                return;
            }int tmp2=Tr[tmp].fa;
            bool flag=son(tmp);
            Tr[tmp].fa=no;Tr[no].fa=tmp2;
            if(flag==0)Tr[tmp2].left=no;
            else Tr[tmp2].right=no;
        }
        void splay(int no){
            while(no!=root){
                if(Tr[no].fa!=root&&son(no)==son(Tr[no].fa))rotate(Tr[no].fa);
                rotate(no);
            }
        }
        void build(int l,int r,int &no,int a[]){
            if(l>r)return;
            if(no==0)no=++nth;
            int mid=(l+r)/2;
            Tr[no].val=a[mid];
            Tr[no].min_val=Tr[no].val;
            build(l,mid-1,Tr[no].left,a);
            if(Tr[no].left){
                Tr[Tr[no].left].fa=no;
                Tr[no].min_val=min(Tr[no].min_val,Tr[Tr[no].left].min_val);
            }
            build(mid+1,r,Tr[no].right,a);
            if(Tr[no].right){
                Tr[Tr[no].right].fa=no;
                Tr[no].min_val=min(Tr[no].min_val,Tr[Tr[no].right].min_val);
            }
            update(no);
        }
        void prework(int len,int a[]){
            for(int i=0;i<100050;i++)Tr[i].val=Tr[i].min_val=1147483647;
            k=len;
            build(0,len+1,root,a);
        }
        int kth(int no){
            if(no==0)return 0;
            tag_pushdown(no);
            if(Tr[Tr[no].left].siz+1==x){
                splay(no);
                return Tr[root].val;
            }if(Tr[Tr[no].left].siz+1>x)return kth(Tr[no].left);
            x-=Tr[Tr[no].left].siz+1;
            return kth(Tr[no].right);
        }
        int kth_num(int val){
            x=val;
            return kth(root);
        }
        void splay_under_root(int no){
            while(Tr[no].fa!=root){
                if(Tr[Tr[no].fa].fa!=root&&son(no)==son(Tr[no].fa))rotate(Tr[no].fa);
                rotate(no);
            }
        }
        int range_min(int l,int r){
            kth_num(r+2);
            int tmp=root;
            kth_num(l);
            splay_under_root(tmp);
            tag_pushdown(root);
            tag_pushdown(tmp);
            tag_pushdown(Tr[Tr[root].right].left);
            Tr[Tr[root].right].min_val=min(Tr[Tr[root].right].min_val,min(Tr[Tr[Tr[root].right].left].min_val,Tr[Tr[Tr[root].right].right].min_val));
            Tr[root].min_val=min(Tr[root].min_val,min(Tr[Tr[root].left].min_val,Tr[Tr[root].right].min_val));
            return Tr[Tr[Tr[root].right].left].min_val;
        }
        void ins(int pos,int val){
            kth_num(pos+2);
            int tmp=root;
            kth_num(pos+1);
            splay_under_root(tmp);
            Tr[Tr[root].right].left=++nth;
            Tr[nth].val=val;
            Tr[nth].fa=Tr[root].right;
            Tr[nth].min_val=Tr[nth].val=val;
            Tr[nth].siz=1;
            Tr[Tr[root].right].siz++;
            Tr[root].siz++;
        }
        void del(int pos){
            kth_num(pos+2);
            int tmp=root;
            kth_num(pos);
            splay_under_root(tmp);
            Tr[Tr[root].right].left=0;
            Tr[Tr[root].right].siz--;
            Tr[root].siz--;
        }
        void range_mov(int l,int r,int stp){
            kth_num(r-stp+2);
            int tmp=root;
            kth_num(l);
            splay_under_root(tmp);
            int Root=Tr[Tr[root].right].left;
            Tr[Tr[root].right].left=0;
            Tr[Tr[root].right].siz-=Tr[Root].siz;
            Tr[root].siz-=Tr[Root].siz;
            kth_num(l+stp+1);
            int tmp2=root;
            kth_num(l+stp);
            splay_under_root(tmp2);
            Tr[Tr[root].right].left=Root;
            Tr[Tr[root].right].siz+=Tr[Root].siz;
            Tr[root].siz+=Tr[Root].siz;
            Tr[Root].fa=Tr[root].right;
        }
        void range_rev(int l,int r){
            kth_num(r+2);
            int tmp=root;
            kth_num(l);
            splay_under_root(tmp);
            Tr[Tr[Tr[root].right].left].tag_rev^=1;
            tag_pushdown(Tr[Tr[root].right].left);
        }
        void range_add(int l,int r,int val){
            kth_num(r+2);
            int tmp=root;
            kth_num(l);
            splay_under_root(tmp);
            Tr[Tr[Tr[root].right].left].tag_add+=val;
            Tr[Tr[Tr[root].right].left].min_val+=val;
            Tr[Tr[Tr[root].right].left].val+=val;
        }
}T;

int n,a[100050],m,x,y,z;
string op;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    a[0]=-1147483647;a[n+1]=1147483647;
    T.prework(n,a);
    cin>>m;
    while(m--){
        cin>>op;
        if(op=="ADD"){
            cin>>x>>y>>z;
            T.range_add(x,y,z);
        }
        if(op=="REVERSE"){
            cin>>x>>y;
            T.range_rev(x,y);
        }
        if(op=="REVOLVE"){
            cin>>x>>y>>z;
            z%=y-x+1;
            if(z)T.range_mov(x,y,z);
        }
        if(op=="INSERT"){
            cin>>x>>y;
            T.ins(x,y);
        }
        if(op=="DELETE"){
            cin>>x;
            T.del(x);
        }
        if(op=="MIN"){
            cin>>x>>y;
            cout<<T.range_min(x,y)<<endl;
        }
    }
    return 0;
}

这道题可以很好地考察你的序列平衡树，细节较多，如果你想透彻平衡树，这道题很值得做.

题外话

高级数据结构代码很长，可读性低？这时候就该显示出 class 的威力了！

我们把封装好的伸展树放在一个头文件里，然后......

#include<iostream>
#include "Data_Structure.h"
using namespace std;

int n,a[100050],m,x,y,z;
string op;

Splay_Tree T;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    a[0]=-1147483647;a[n+1]=1147483647;
    T.prework(n,a);
    cin>>m;
    while(m--){
        cin>>op;
        if(op=="ADD"){
            cin>>x>>y>>z;
            T.range_add(x,y,z);
        }
        if(op=="REVERSE"){
            cin>>x>>y;
            T.range_rev(x,y);
        }
        if(op=="REVOLVE"){
            cin>>x>>y>>z;
            z%=y-x+1;
            if(z)T.range_mov(x,y,z);
        }
        if(op=="INSERT"){
            cin>>x>>y;
            T.ins(x,y);
        }
        if(op=="DELETE"){
            cin>>x;
            T.del(x);
        }
        if(op=="MIN"){
            cin>>x>>y;
            cout<<T.range_min(x,y)<<endl;
        }
    }
    return 0;
}

是不是清爽多了！（滑稽）