[题解] Luogu P2042 [NOI2005]维护数列

@ajcxsu  January 20, 2018 

大概是Splay的新手村最终关。
写完这个大概就算入了门。
S树受虐全集-从入门到入土
56935221_p0.jpg

Problem

请写一个程序,要求维护一个数列,支持以下 6 种操作:(请注意,格式栏 中的下划线‘ _ ’表示实际输入文件中的空格)
1114.jpg

Solution

本题我们从几个方面来阐述。
第一,文艺平衡树你得会写。
第二,你至少得写过其它一个维护区间的题目。
第三,你会线段树。你知道lazy的思想。
第四,本题我使用的是不维护父指针递归版本。
那么我们开始。细节我们一个一个来。

Struct

总而言之,我们要维护:
序列插入/删除/翻转/整体更改操作。序列和。子序列最大和。

许多操作我们将用到线段树的思想。
线段树是用一个棵二叉树,每个点表示一个区间,是二分的思想。而换到平衡树里面来,我们发现,每一颗子树的范围也是一个区间。所以在平衡树中,我们使用子树的根节点代表一个区间。
如果根节点能够维护子树的区间的话,那我们只需要提取那个区间的子树,输出子树根节点的信息就行了。
这就是平衡树中的线段树思想。而复杂度也是log(n)的。且目前,我只知道splay能做到这种操作。

那么既然要用点维护子树序列的信息,我们需要用结构体保存以下信息。

struct Node {
    int v,s,c;
    Node *ch[2];
    int lx,rx,mx,sum;
    bool t1,t2; // tag1 -> chg; tag2 -> rev
    ...

前几个我就不用说了。
第四行开始是维护子树序列的信息。前三维护最大子序列,后一维护和。
第五行维护的是lazy标记。
干嘛用的我们一个个说。

Basic Operation

k大比较函数,pushdown,pushup(包括了更新子树大小操作/子树序列变化之后的更新操作)等。
pushup就是因为你旋转之后子树可能改变,那么子树代表的序列就改变了,因此你需要更新新子树序列的根节点。就是这种操作。

Insert

Initalization

因为我不会构造完美平衡树所以我用了另一个方法。大概是O(3n)。

/* Input */
    root=new Node(-INF), root->sum=0;
    Node *nd=root;
    int v;
    for(int i=1;i<=n;i++) gn(v), nd->ch[1]=new Node(v), nd=nd->ch[1];
    nd->ch[1]=new Node(-INF), nd->ch[1]->sum=0;
    splay(root,INF); // upd tag

概括如下:
在根节点构造一个虚点——这是维护区间必须的操作。
之后我们一直向右构建节点。
n个节点构建完之后,再往右加一个虚点。
之后,把最后一个点旋到根。由于我们在加点的时候并没有更新节点的其它信息,所以我们必须要通过这个操作将树的所有节点状态更新到最新,不然可能影响后面的操作。
并且,这样构造时虽然没有更新节点的其它信息(比如子树大小),但是在短时间内并不影响排名的查询。所以不会影响到splay的操作。

构造一遍O(n),旋上来一遍O(2n),我们可以发现这么做时间复杂度并不差。
上方代码还有一些其它的细节,我们一会儿讲。

Insert Operation

至于插入操作,我们可以用同样的方法。
在l插入tot个节点,我们把l-1旋到根,l旋到根的右儿子。然后以l的左儿子为根,开始进行同样的构造。而且同样要更新所有点的信息。
之后我们再把l和l-1都给pushup一下就行了。

void insert(int l,int tot) {
    splay(root, l-1), splay(root->ch[1],1);
    int v;
    gn(v);
    root->ch[1]->ch[0]=new Node(v);
    Node *nd=root->ch[1]->ch[0];
    for(int i=2;i<=tot;i++) gn(v),nd->ch[1]=new Node(v), nd=nd->ch[1];
    splay(root->ch[1]->ch[0], INF); // upd tag
    root->ch[1]->pup(), root->pup();
}

Delete

由于本题的空间限制较为严格,因此我们得递归删除节点。
跟普通的删除一样。记得把根节点和根节点儿子都给pushup。

namespace Delete {
    void dfs(Node *x) {
        if(x==nil) return;
        Delete::dfs(x->ch[0]), Delete::dfs(x->ch[1]);
        delete x;
    }
    void main(int l,int r) {
        splay(root,l-1), splay(root->ch[1],r+2-l);
        Delete::dfs(root->ch[1]->ch[0]);
        root->ch[1]->ch[0]=nil;
        root->ch[1]->pup(), root->pup(); // upd tag
    }
}

Reverse

翻转还是一样。
但跟求最大子序列搭配起来有一些变化。这个我们之后讲。
而且我们采取即使更新当个节点的策略,lazy只用于更新下方节点,即与线段树相同。

Largest subsequence

重头戏来了。

我们先回想一下怎么用线段树求最大子序列。
使用lx,rx,mx,分别代表当前区间前缀最大子序列和,后缀最大子序列和,和当前区间的最大子序列和。
我们采用分治的思想,得到如下的方程:

lx[x]=max(lx[ls],sum[ls]+lx[rs]);
rx[x]=max(rx[rs],sum[rs]+rx[ls]);
mx[x]=max(mx[lx],mx[rx],rx[ls]+lx[rs]);

这个方程还有些细节。即如果这个区间的左(右)前缀序列最大和本来就低于0了,那我们就不选,即认为其等于0。mx[x]最小也得包含一个元素,那么如果全部小于0就选区间里的最大元素。

变成splay的话就是:

lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
mx=max(ch[0]->mx,max(ch[1]->mx,ch[0]->rx+v+ch[1]->lx));

我们稍作思考就发现,这个方程囊括了所有可能的情况。
其中之一如果lx,rx都等于0,那么mx会等于这个区间的最大元素。
其它情况就不多说了。

初始情况也很容易想。这里我们将整个结构体的构造函数放上来:

    Node (int val=0): v(val),s(1),c(1),sum(val),mx(val),t1(0),t2(0) { 
        ch[0]=ch[1]=nil;
        if(val>=0) lx=rx=val;
        else lx=rx=0;
    }

Pushup操作的内容也水到渠成:

    inline void pup() {
        s=c+ch[0]->s+ch[1]->s;
        sum=ch[0]->sum+v+ch[1]->sum;
        lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
        rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
        mx=max(ch[0]->mx,max(ch[1]->mx,ch[0]->rx+v+ch[1]->lx));
    }

但是这里还有一个问题:我们不是构造了哨兵节点和头尾的虚点吗?这几个点在Pushup上的影响该怎么避免?
我们先说哨兵节点。哨兵节点不应该对判断造成任何影响,以至于它应该被方程所有情况避免。那么将其sum/ls/rs置为0,mx置为-INF是个不错的选择。
那么头尾的虚点呢?头尾的虚点是可能做根节点的。因此我们这么做:v置为-INF,与此同时,如果它作为叶子节点,那么它的mx会被置为-INF。如果不作为叶子节点,那么对于它方程等价于:

lx=ch[0]->lx;
rx=ch[1]->rx;
mx=max(ch[0]->mx,ch[1]->mx);

同时这两个点肯定代表着某个区间的末尾/开头。那么这些虚点的影响就消失了。
但是sum要置为0.

此时构造哨兵节点的函数就出来了。

inline void clr() { ch[0]=ch[1]=nil, v=0, s=c=0, lx=rx=sum=t1=t2=0, mx=-INF; }
...
void init() {
    nil=new Node(-INF);
    nil->clr();
}

与此同时,由于翻转之后整个区间都反了过来,因此根节点的lx和rx也要交换。
翻转的函数变成如下:

void rev(int l,int r) {
    splay(root,l-1), splay(root->ch[1],r+2-l);
    Node *rt=root->ch[1]->ch[0];
    if(rt->t1==-INF) return;
    rt->t2^=1;
    swap(rt->ch[0],rt->ch[1]), swap(rt->lx,rt->rx); // attention
    root->ch[1]->pup(), root->pup(); // attention
}

Modify

修改很简单。但是要给节点的lx,rx,mx更改,还是有点麻烦的。

void chg(int l,int r,int v) {
    splay(root,l-1), splay(root->ch[1],r+2-l);
    Node *rt=root->ch[1]->ch[0];
    rt->v=v,rt->sum=rt->s*v;
    if(v>=0) rt->lx=rt->rx=rt->mx=rt->sum;
    else rt->lx=rt->rx=0, rt->mx=v; // attention
    rt->t1=1;
    root->ch[1]->pup(), root->pup();
}

讲完Modify和Reverse,那么Pushdown函数也就出来了。

    inline void pud() {
        if(t1) {
            t1=t2=0; // 如果全部赋为同一个值就不用翻转了
            _rg Node *l=ch[0],*r=ch[1];
            l->t1=1, l->v=v, l->sum=l->s*v;
            r->t1=1, r->v=v, r->sum=r->s*v;
            if(v>=0) {
                l->lx=l->rx=l->mx=l->sum;
                r->lx=r->rx=r->mx=r->sum;
            }
            else {
                l->lx=l->rx=0, l->mx=v;
                r->lx=r->rx=0, r->mx=v;
            }
        }
        if(t2) {
            t2=0;
            _rg Node *l=ch[0], *r=ch[1];
            l->t2^=1, r->t2^=1;
            swap(l->ch[0],l->ch[1]), swap(r->ch[0],r->ch[1]);
            swap(l->lx,l->rx), swap(r->lx,r->rx); // attention
        }
        nil->clr(); // attention
    }

Query

查询操作我们不再解释。

Code

// Code by ajcxsu
// Problem: P2042

#include<bits/stdc++.h>
#define _rg register
#define INF (0x3f3f3f3f)
using namespace std;

int n,m;
inline int max(const int &x, const int &y) { return x>y?x:y; }
inline int min(const int &x, const int &y) { return x<y?x:y; }
inline void gn(int &x) {
    x=0;
    _rg int pl=1;
    _rg char ch=getchar();
    while(ch<'0' || ch>'9') pl=(ch=='-'?-1:1), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=pl;
}

inline char gb() {
    _rg char ch=getchar();
    while(ch<'A' || ch>'Z') ch=getchar();
    return ch;
}

/* splay */
struct Node *nil;
struct Node {
    int v,s,c;
    Node *ch[2];
    int lx,rx,mx,sum;
    bool t1,t2; // tag1 -> chg; tag2 -> rev

    Node (int val=0): v(val),s(1),c(1),sum(val),mx(val),t1(0),t2(0) { 
        ch[0]=ch[1]=nil;
        if(val>=0) lx=rx=val;
        else lx=rx=0;
    }
    inline int cmp(int &k) {
        if(k<=ch[0]->s) return 0;
        else if(k<=ch[0]->s+c) return -1;
        else { k-=ch[0]->s+c; return 1; }
    }
    inline void clr() { ch[0]=ch[1]=nil, v=0, s=c=0, lx=rx=sum=t1=t2=0, mx=-INF; }
    inline void pud() {
        if(t1) {
            t1=t2=0;
            _rg Node *l=ch[0],*r=ch[1];
            l->t1=1, l->v=v, l->sum=l->s*v;
            r->t1=1, r->v=v, r->sum=r->s*v;
            if(v>=0) {
                l->lx=l->rx=l->mx=l->sum;
                r->lx=r->rx=r->mx=r->sum;
            }
            else {
                l->lx=l->rx=0, l->mx=v;
                r->lx=r->rx=0, r->mx=v;
            }
        }
        if(t2) {
            t2=0;
            _rg Node *l=ch[0], *r=ch[1];
            l->t2^=1, r->t2^=1;
            swap(l->ch[0],l->ch[1]), swap(r->ch[0],r->ch[1]);
            swap(l->lx,l->rx), swap(r->lx,r->rx);
        }
        nil->clr();
    }
    inline void pup() {
        s=c+ch[0]->s+ch[1]->s;
        sum=ch[0]->sum+v+ch[1]->sum;
        lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
        rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
        mx=max(ch[0]->mx,max(ch[1]->mx,ch[0]->rx+v+ch[1]->lx));
    }
} *root;
void init() {
    nil=new Node(-INF);
    nil->clr();
}

void rot(Node *&x, bool type) {
    Node *t=x->ch[type];
    x->ch[type]=t->ch[!type];
    t->ch[!type]=x;
    x->pup(), t->pup();
    x=t;
}

void splay(Node *&x, int k) {
    x->pud();
    int d=x->cmp(k);
    if(d!=-1 && x->ch[d]!=nil) {
        Node *&y=x->ch[d];
        y->pud();
        int d2=y->cmp(k);
        if(d2!=-1 && y->ch[d2]!=nil) {
            splay(y->ch[d2], k);
            if(d==d2) rot(x,d), rot(x,d);
            else rot(y,d2), rot(x,d);
        }
        else rot(x,d);
    }
}

void insert(int l,int tot) {
    splay(root, l-1), splay(root->ch[1],1);
    int v;
    gn(v);
    root->ch[1]->ch[0]=new Node(v);
    Node *nd=root->ch[1]->ch[0];
    for(int i=2;i<=tot;i++) gn(v),nd->ch[1]=new Node(v), nd=nd->ch[1];
    splay(root->ch[1]->ch[0], INF); // upd tag
    root->ch[1]->pup(), root->pup();
}

namespace Delete {
    void dfs(Node *x) {
        if(x==nil) return;
        Delete::dfs(x->ch[0]), Delete::dfs(x->ch[1]);
        delete x;
    }
    void main(int l,int r) {
        splay(root,l-1), splay(root->ch[1],r+2-l);
        Delete::dfs(root->ch[1]->ch[0]);
        root->ch[1]->ch[0]=nil;
        root->ch[1]->pup(), root->pup(); // upd tag
    }
}

void rev(int l,int r) {
    splay(root,l-1), splay(root->ch[1],r+2-l);
    Node *rt=root->ch[1]->ch[0];
    if(rt->t1==-INF) return;
    rt->t2^=1;
    swap(rt->ch[0],rt->ch[1]), swap(rt->lx,rt->rx); // attention
    root->ch[1]->pup(), root->pup(); // attention
}

int gsum(int l,int r) {
    splay(root,l-1), splay(root->ch[1],r+2-l);
    return root->ch[1]->ch[0]->sum;
}

void chg(int l,int r,int v) {
    splay(root,l-1), splay(root->ch[1],r+2-l);
    Node *rt=root->ch[1]->ch[0];
    rt->v=v,rt->sum=rt->s*v;
    if(v>=0) rt->lx=rt->rx=rt->mx=rt->sum;
    else rt->lx=rt->rx=0, rt->mx=v; // attention
    rt->t1=1;
    root->ch[1]->pup(), root->pup();
}

int main() {
    init();
    gn(n),gn(m);
    /* Input */
    root=new Node(-INF), root->sum=0;
    Node *nd=root;
    int v;
    for(int i=1;i<=n;i++) gn(v), nd->ch[1]=new Node(v), nd=nd->ch[1];
    nd->ch[1]=new Node(-INF), nd->ch[1]->sum=0;
    splay(root,INF); // upd tag

    /* Solve */
    char opt[100];
    int a,b,c;
    while(m--) {
        scanf("%s",opt);
        if(opt[0]=='I') gn(a),gn(b),a+=2,insert(a,b);
        else if(opt[0]=='D') gn(a),gn(b),a++,Delete::main(a,a+b-1);
        else if(opt[0]=='R') gn(a),gn(b),a++,rev(a,a+b-1);
        else if(opt[0]=='G') gn(a),gn(b),a++,printf("%d\n",gsum(a,a+b-1));
        else if(opt[0]=='M'&& opt[2]=='K') gn(a),gn(b),gn(c),a++,chg(a,a+b-1,c);
        else printf("%d\n",root->mx);
    }
    return 0;
}

感谢I_AM_HELLOWORLD的题解


添加新评论