题解：P10689 SuperMemo

Antarctica_Oabaijnaw · 2025-01-04 11:46:10 · 题解

题目大意

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

ADD x y D 将 A_x 到 A_y 加 D；
REVERSE x y 翻转 A_x 到 A_y；
REVOLVE x y T 执行 T 次将 A_y 移动到 A_x 之前的操作；
INSERT x P 将 P 插入到 A_x 之后；
DELETE x 删除 A_x；
MIN x y 查询 A_x 到 A_y 的最小值；

喜欢 Splay 指针版的同志们有福啦！

谨以此题解纪念此题卡我 26 次的恩情！

众所周知，我们做此类区间操作的题目，都是用 FHQ-treap 或者 splay。由第一句可得，这是一篇 splay 的题解。不会 splay 区间操作的右转【模板】文艺平衡树。

由于蒟蒻的指针版码风过于离谱，先把基础操作放前面：

里面有 newnode, rotate, splay, pushup, pushdown, select 操作。

struct node{
    node *ch[2],*fa;
    int siz;
    long long tag/*添加标记*/,minn/*最小值*/,val/*节点值*/;
    bool flag/*旋转标记*/;
}tree[1000005];
node *root/*根*/,*NIL/*空节点*/,*ncnt/*新建节点*/;
void init(){
    NIL=ncnt=&tree[0];
    NIL->minn=NIL->val=1e16;
    NIL->ch[0]=NIL->ch[1]=NIL->fa=NIL;
}
node *newnode(long long val){//新建节点
    node *p=++ncnt;
    p->ch[0]=p->ch[1]=p->fa=NIL;
    p->val=p->minn=val;
    p->siz=1;
    return p;
}
void rotate(node *x){//旋转
    node *y=x->fa;
    int d=(x==y->ch[0]);
    x->fa=y->fa;
    if(y->fa!=NIL)y->fa->ch[y==y->fa->ch[1]]=x;
    y->ch[!d]=x->ch[d]; 
    if(x->ch[d]!=NIL)x->ch[d]->fa=y;
    x->ch[d]=y;
    y->fa=x;
    if(root==y)root=x;
    pushup(y);
    pushup(x);
}
void splay(node *x,node *rt){//伸展
    node *y,*z;
    while(x->fa!=rt){
        y=x->fa;
        z=y->fa;
        if(z==rt)rotate(x);
        else{
            if((x==y->ch[0])^(y==z->ch[0]))rotate(x);
            else rotate(y);
            rotate(x);
        }
    }
}
void pushup(node *rt){
    if(rt==NIL)return;
    rt->siz=rt->ch[0]->siz+rt->ch[1]->siz+1;
    rt->minn=min({rt->val,rt->ch[0]->minn,rt->ch[1]->minn});
}
void pushdown(node *rt){
    if(rt->flag){
        swap(rt->ch[0],rt->ch[1]);
        if(rt->ch[0]!=NIL)rt->ch[0]->flag^=1;
        if(rt->ch[1]!=NIL)rt->ch[1]->flag^=1;
        rt->flag=0;
    }
    if(rt->tag){
        if(rt->ch[0]!=NIL){
            rt->ch[0]->tag+=rt->tag;
            rt->ch[0]->val+=rt->tag;
            rt->ch[0]->minn+=rt->tag;
        }
        if(rt->ch[1]!=NIL){
            rt->ch[1]->tag+=rt->tag;
            rt->ch[1]->val+=rt->tag;
            rt->ch[1]->minn+=rt->tag;
        }
        rt->tag=0;
    }
}
node *select(int k,node *fa){//根据排名查询值
    node *p=root;
    while(true){
        pushdown(p);
        if(p->ch[0]->siz+1>k)p=p->ch[0];
        else if(p->ch[0]->siz+1==k)break;
        else k-=(p->ch[0]->siz+1),p=p->ch[1];
    }
    splay(p,fa);
    return p;
}

注：由于加了哨兵节点，下文所有 select 操作第一个参数（即排名）都比预期的要多 1。

Step 1：建树

~~我不会告诉你我以前建树都是直接无脑用 insert 函数。~~

由于此题太过毒瘤，我们使用专门的建树函数，将序列建成一棵近似于完全二叉树的形状。

node *build(int l,int r){
    if(l>r)return NIL;
    int mid=(l+r)>>1;
    node *p=build(l,mid-1),*q=build(mid+1,r),*now=newnode(a[mid]);
    now->ch[0]=p;
    now->ch[1]=q;
    if(p!=NIL)p->fa=now;
    if(q!=NIL)q->fa=now;
    pushup(now);
    return now;
}

记得在主函数加上这么一句 root=build(0,n+1);。

Step 2：ADD && REVERSE 操作

做过【模板】文艺平衡树都会的操作，标记即可。

if(op=="ADD"){
    int l,r,k;
    cin>>l>>r>>k;
    node *p=select(l,NIL),*q=select(r+2,p);
    q->ch[0]->tag+=k;
    q->ch[0]->val+=k;
    q->ch[0]->minn+=k;
}else if(op=="REVERSE"){
    int l,r;
    cin>>l>>r;
    node *p=select(l,NIL),*q=select(r+2,p);
    q->ch[0]->flag^=1;
}

Step 3：INSERT && DELETE 操作

本代码使用的 select 函数使得这两个操作变得尤为简便，代码如下：

if(op=="INSERT"){
    int x,k;
    cin>>x>>k;
    node *p=select(x+1,NIL),*q=select(x+2,p);
    node *nw=newnode(k);
    q->ch[0]=nw;
    nw->fa=q;
}else if(op=="DELETE"){
    int x;
    cin>>x;
    node *p=select(x,NIL),*q=select(x+2,p);
    q->ch[0]=NIL;
}

Step 4：REVOLVE 操作

重中之重！（蒟蒻就是因为特别构式的代码连 WA 20 余发，最后大改了一遍才 AC 的）

首先把 T 对 y-x+1 取模。

我们注意到（~~注意力惊人~~）REVOLVE 操作就表示将区间 [y-T+1,y] 移到 x 之前，于是就有下文的代码：

if(op=="REVOLVE"){
    int l,r,d;
    cin>>l>>r>>d;
    d%=(r-l+1);
    if(d==0)continue;
    node *p=select(r-d+1,NIL),*q=select(r+2,p);
    node *tr=q->ch[0];
    q->ch[0]=NIL;
    p=select(l,NIL),q=select(l+1,p);
    q->ch[0]=tr;
    tr->fa=q;
}

Step 5：MIN 操作

最简单的操作。

if(op=="MIN"){
    int l,r;
    cin>>l>>r;
    node *p=select(l,NIL),*q=select(r+2,p);
    cout<<q->ch[0]->minn<<endl;
}

终于结束了（狂喜！）

完整代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n,m;
struct node{
    node *ch[2],*fa;
    int siz;
    long long tag,minn,val;
    bool flag;
}tree[1000005];
node *root,*NIL,*ncnt;
void init(){
    NIL=ncnt=&tree[0];
    NIL->minn=NIL->val=1e16;
    NIL->ch[0]=NIL->ch[1]=NIL->fa=NIL;
}
node *newnode(long long val){
    node *p=++ncnt;
    p->ch[0]=p->ch[1]=p->fa=NIL;
    p->val=p->minn=val;
    p->siz=1;
    return p;
}
void pushup(node *rt){
    if(rt==NIL)return;
    rt->siz=rt->ch[0]->siz+rt->ch[1]->siz+1;
    rt->minn=min({rt->val,rt->ch[0]->minn,rt->ch[1]->minn});
}
void pushdown(node *rt){
    if(rt->flag){
        swap(rt->ch[0],rt->ch[1]);
        if(rt->ch[0]!=NIL)rt->ch[0]->flag^=1;
        if(rt->ch[1]!=NIL)rt->ch[1]->flag^=1;
        rt->flag=0;
    }
    if(rt->tag){
        if(rt->ch[0]!=NIL){
            rt->ch[0]->tag+=rt->tag;
            rt->ch[0]->val+=rt->tag;
            rt->ch[0]->minn+=rt->tag;
        }
        if(rt->ch[1]!=NIL){
            rt->ch[1]->tag+=rt->tag;
            rt->ch[1]->val+=rt->tag;
            rt->ch[1]->minn+=rt->tag;
        }
        rt->tag=0;
    }
}
void rotate(node *x){
    node *y=x->fa;
    int d=(x==y->ch[0]);
    x->fa=y->fa;
    if(y->fa!=NIL)y->fa->ch[y==y->fa->ch[1]]=x;
    y->ch[!d]=x->ch[d]; 
    if(x->ch[d]!=NIL)x->ch[d]->fa=y;
    x->ch[d]=y;
    y->fa=x;
    if(root==y)root=x;
    pushup(y);
    pushup(x);
}
void splay(node *x,node *rt){
    node *y,*z;
    while(x->fa!=rt){
        y=x->fa;
        z=y->fa;
        if(z==rt)rotate(x);
        else{
            if((x==y->ch[0])^(y==z->ch[0]))rotate(x);
            else rotate(y);
            rotate(x);
        }
    }
}
void insert(node *&rt,node *p,long long val){
    if(rt==NIL){
        rt=newnode(val);
        rt->fa=p;
        splay(rt,NIL);
        return;
    }
    rt->siz++;
    insert(rt->ch[1],rt,val);
}
node *select(int k,node *fa){
    node *p=root;
    while(true){
        pushdown(p);
        if(p->ch[0]->siz+1>k)p=p->ch[0];
        else if(p->ch[0]->siz+1==k)break;
        else k-=(p->ch[0]->siz+1),p=p->ch[1];
    }
    splay(p,fa);
    return p;
}
long long a[100005];
node *build(int l,int r){
    if(l>r)return NIL;
    int mid=(l+r)>>1;
    node *p=build(l,mid-1),*q=build(mid+1,r),*now=newnode(a[mid]);
    now->ch[0]=p;
    now->ch[1]=q;
    if(p!=NIL)p->fa=now;
    if(q!=NIL)q->fa=now;
    pushup(now);
    return now;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    a[0]=a[n+1]=1e16;//哨兵节点
    root=build(0,n+1);
    cin>>m;
    while(m--){
        string op;
        cin>>op;
        if(op=="ADD"){
            int l,r,k;
            cin>>l>>r>>k;
            node *p=select(l,NIL),*q=select(r+2,p);
            q->ch[0]->tag+=k;
            q->ch[0]->val+=k;
            q->ch[0]->minn+=k;
        }else if(op=="REVERSE"){
            int l,r;
            cin>>l>>r;
            node *p=select(l,NIL),*q=select(r+2,p);
            q->ch[0]->flag^=1;
        }else if(op=="REVOLVE"){
            int l,r,d;
            cin>>l>>r>>d;
            d%=(r-l+1);
            if(d==0)continue;
            node *p=select(r-d+1,NIL),*q=select(r+2,p);
            node *tr=q->ch[0];
            q->ch[0]=NIL;
            p=select(l,NIL),q=select(l+1,p);
            q->ch[0]=tr;
            tr->fa=q;
        }else if(op=="INSERT"){
            int x,k;
            cin>>x>>k;
            node *p=select(x+1,NIL),*q=select(x+2,p);
            node *nw=newnode(k);
            q->ch[0]=nw;
            nw->fa=q;
        }else if(op=="DELETE"){
            int x;
            cin>>x;
            node *p=select(x,NIL),*q=select(x+2,p);
            q->ch[0]=NIL;
        }else if(op=="MIN"){
            int l,r;
            cin>>l>>r;
            node *p=select(l,NIL),*q=select(r+2,p);
            cout<<q->ch[0]->minn<<endl;
        }
    }
}