「LuoguP2042」「NOI2005」维护数列

AutumnKite

题解Luogu

发布于：2019年1月15日

次浏览

题目传送门

题意

维护一个序列，支持插入序列、区间删除、区间覆盖、区间翻转、区间求和、求序列最大子段和（至少包含一个元素）。

插入总数\(\le 4\times 10^6\)，任意时刻序列长度\(\le 5\times 10^5\)。

题解

\(Splay\)板子题。

不会\(Splay\)的同学出门左转文艺平衡树。

由于插入数量太大，直接开4000000的数组显得不现实，我们考虑建立回收栈（雾），删除时遍历子树，回收被删除的节点，新建节点时优先从回收栈里取点，但是要注意各个数组都要初始化。

总体思路是，对每个节点维护：\(val,sz,sum,la,ra,ma\)，分别表示这个点本身的值、子树大小、子树的\(val\)之和、该区间（以这个点为根的子树所表示的区间，下同）中包含最左边元素的最长子段和（可以不包含元素）、包含最右边元素的最长子段和（可以不包含元素）、整个区间的最大子段和（至少包含一个元素，即答案）；懒标记\(cov=0/1,rev=0/1\)，分别表示该区间是否被覆盖、是否被翻转。

接下来我们仔细分析每一步操作。

新建节点

已经讲过，若回收栈里有点，则优先拿来用，否则新建节点。

int new_node(int _val){
    int x = top ? rb[top--] : ++cnt; // rb即回收栈
    son[x][0] = son[x][1] = fa[x] = rev[x] = cov[x] = 0, sz[x] = 1; // 注意别忘记初始化
    val[x] = ma[x] = sum[x] = _val, la[x] = ra[x] = std :: max(_val, 0); // la,ra可以不包含元素
    return x;
}

上传

主要是\(la,ra,ma\)的更新。\(la\)和\(ra\)同理，以\(la\)为例，当前节点的\(la\)值就是max(左子树的la,左子树的sum+当前节点的val+右子树的la)，分别表示跨过当前节点和不跨过当前节点两种情况。对于\(ma\)，也差不多，不跨过的情况是max(左子树的ma,右子树的ma)，跨过的情况是左子树的ra+当前节点的val+右子树的la，在这两种情况中再取个\(max\)即可。

void up(int u){
    int ls = son[u][0], rs = son[u][1];
    sz[u] = sz[ls] + sz[rs] + 1, sum[u] = sum[ls] + sum[rs] + val[u];
    la[u] = std :: max(la[ls], sum[ls] + val[u] + la[rs]);
    ra[u] = std :: max(ra[rs], sum[rs] + val[u] + ra[ls]);
    ma[u] = std :: max(std :: max(ma[ls], ma[rs]), ra[ls] + val[u] + la[rs]);
}

下传懒标记

比较简单，不需要考虑标记下传的顺序。

对于\(cov\)标记，直接把左右儿子的\(val\)设为当前节点的\(val\)，\(sum\)设为\(val\times sz\)。而\(la,ra,ma\)则需要分类讨论，若\(val>0\)，显然直接把整个区间选上更优，否则\(la,ra\)不选，\(ma\)只选一个点。

对于\(rev\)标记，直接交换左右儿子的左右子树、左右儿子的\(la,ra\)（注意不是交换当前节点的左右子树、\(la,ra\)，这种写法在文艺平衡树可以过，但是在本题中会出错）。

void down(int u){
    int ls = son[u][0], rs = son[u][1];
    if (cov[u]){
        if (ls) val[ls] = val[u], cov[ls] = 1, sum[ls] = sz[ls] * val[u];
        if (rs) val[rs] = val[u], cov[rs] = 1, sum[rs] = sz[rs] * val[u];
        if (val[u] > 0){ // 分类讨论
            if (ls) la[ls] = ra[ls] = ma[ls] = sum[ls];
            if (rs) la[rs] = ra[rs] = ma[rs] = sum[rs];
        }
        else{
            if (ls) la[ls] = ra[ls] = 0, ma[ls] = val[u];
            if (rs) la[rs] = ra[rs] = 0, ma[rs] = val[u];
        }
        cov[u] = 0;
    }
    if (rev[u]){
        if (ls) rev[ls] ^= 1, std :: swap(son[ls][0], son[ls][1]), std :: swap(la[ls], ra[ls]);
        if (rs) rev[rs] ^= 1, std :: swap(son[rs][0], son[rs][1]), std :: swap(la[rs], ra[rs]);
        // 交换左右儿子的左右子树和la,ra
        rev[u] = 0;
    }
}

建树

直接按照原序列的顺序建树（注意不是按数的大小建树）。

可是直接插入是\(\mathcal O(n\log n)\)的，且常数较大。我们直接取序列中点作为根，然后递归调用左边和右边，分别作为根的左儿子和右儿子。

这样我们可以做到\(\mathcal O(n)\)建树，\(n\)是序列长度。

int build(int l, int r, int *a){
    if (l > r) return 0;
    if (l == r) return new_node(a[l]);
    int mid = (l + r) >> 1, u = new_node(a[mid]);
    // 以mid为该子树的根，递归处理左右两边
    son[u][0] = build(l, mid - 1, a), son[u][1] = build(mid + 1, r, a);
    fa[son[u][0]] = fa[son[u][1]] = u;
    return up(u), u; // 注意更新
}

Splay的基本操作：\(rotate(x)\)和\(splay(x,g)\)

\(rotate(x)\)表示将\(x\)向上旋转，\(splay(x,g)\)表示将\(x\)旋转到\(g\)的儿子。

注意\(rotate(x)\)时需要上传操作，且要注意操作顺序。\(splay(x,g)\)需要双旋。

int dir(int x){ return son[fa[x]][1] == x; } // 返回x是他父亲的哪个儿子
void set(int x, int k, int y){ son[x][k] = y, fa[y] = x; } // 将x的k儿子变成y
void rotate(int x){
    int y = fa[x], d = dir(x);
    set(fa[y], dir(y), x), set(y, d, son[x][!d]), set(x, !d, y);
    up(y), up(x); // 注意上传以及上传的顺序
}
void splay(int x, int g = 0){ // g=0相当于旋转到根上
    while (fa[x] != g){
        int y = fa[x];
        if (fa[y] != g) dir(y) == dir(x) ? rotate(y) : rotate(x);
        rotate(x); // 双旋
    }
    if (!g) rt = x; // 更新rt
}

求当前序列中第\(k\)个位置在Splay中对应的节点

这是下面前五个操作中必需的一个操作，即把序列中的位置转化为树上的节点编号。

这是一个经典的求第\(k\)小的问题，直接按照左子树的\(sz\)和当前的\(k\)的大小关系决定往左、往右还是直接返回当前节点。

注意，此时由于需要用到儿子的信息，我们必须把\(u\)的标记下传。

且因为这样做会把根到要求的那个节点的路径上的所有节点都\(down\)一遍，所以在其余操作中不需要再进行\(down\)操作。

int kth(int u, int k){
    down(u); // 下传标记
    int ls = son[u][0], rs = son[u][1];
    if (k == sz[ls] + 1) return u; // 直接返回
    else if (k <= sz[ls]) return kth(ls, k); // 向左走
    else return kth(rs, k - sz[ls] - 1); // 向右走
}

插入操作

对于插入操作，我们直接把\(pos\)对应的节点\(splay\)到根上（记为\(u\)），把\(pos+1\)的位置旋转到根下面（记为\(v\)，即此时\(fa[v]=u\)）。此时\(v\)的左子树一定为空（不存在一个整数\(x\)满足\(pos<x<pos+1\)）。那么直接把需要插入的序列\(\mathcal O(n)\)建树，把根节点连到\(v\)上，作为\(v\)的左子树即可。

void insert(int x, int tot, int *a){
    int t = build(1, tot, a);
    int u = kth(rt, x); splay(u);
    int v = kth(rt, x + 1); splay(v, u);
    son[v][0] = t, fa[t] = v, up(v), up(u);
    // 注意别忘记fa[t]=v和上传标记，不要习惯性打成up(u),up(v)
}

删除操作

假设我们要删除的是区间\([l,r]\)，那么同理，我们把\(l-1\)对应的节点旋转到根上（记为\(u\)），把\(r+1\)的位置旋转到根下面（记为\(v\)，即此时\(fa[v]=u\)）。

此时\(v\)的左子树所表示的区间即为\([l,r]\)，那么我们直接把\(v\)的左子树删除即可。

void recycle(int u){ // 回收以u为根的子树
    int ls = son[u][0], rs = son[u][1];
    if (ls) recycle(ls);
    if (rs) recycle(rs);
    rb[++top] = u;
}
void erase(int l, int r){
    int u = kth(rt, l - 1); splay(u);
    int v = kth(rt, r + 1); splay(v, u); // 提区间操作
    recycle(son[v][0]), son[v][0] = 0, up(v), up(u); // 更新
}

覆盖操作

与删除同理，提取区间\([l,r]\)，打上\(cov\)标记，更新即可。

void cover(int l, int r, int c){
    int u = kth(rt, l - 1); splay(u);
    int v = kth(rt, r + 1); splay(v, u);
    int t = son[v][0]; // 提区间
    val[t] = c, cov[t] = 1, sum[t] = sz[t] * c;
    if (c > 0) la[t] = ra[t] = ma[t] = sum[t];
    else la[t] = ra[t] = 0, ma[t] = c; // 打标记，与down中同理
    up(v), up(u); // 更新
}

翻转操作

同理，提取区间后，打上\(rev\)标记并更新。

void reverse(int l, int r){
    int u = kth(rt, l - 1); splay(u);
    int v = kth(rt, r + 1); splay(v, u);
    int t = son[v][0]; // 提区间
    rev[t] ^= 1, std :: swap(son[t][0], son[t][1]), std :: swap(la[t], ra[t]);
    // 打标记，与down中同理
    up(v), up(u); // 更新
}

求和操作

提取区间后直接输出\(sum\)值即可，不需要更新。

void query_sum(int l, int r){
    int u = kth(rt, l - 1); splay(u);
    int v = kth(rt, r + 1); splay(v, u);
    printf("%d\n", sum[son[v][0]]);
}

最大子段和

直接输出\(ma[rt]\)即可。

一些细节

由于\(pos,l-1\)可能会\(<1\)，\(pos+1,r\)可能会\(>n\)，所以要考虑边界问题。我的代码中是直接把整个数组向右移动一位，并且使\(a[1]=a[n+2]=-\text{INF}\)。个人觉得这个方法比较简单，只要在主程序中做一些简单的处理即可。
由于\(up\)中没有判断左儿子或右儿子为空的情况（判起来会变得很鬼畜），所以我们令\(ma[0]=-\text{INF}\)。

代码实现

总的再发一次吧。吸氧后~~最快的一次~~共1111ms。评测记录

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
int read(){
    register int x = 0, f = 1;
    register char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = !f;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
    return f ? x : -x;
}
#define N 500005
#define INF 500000000
int n, m, a[N];
char opt[15];
int k, x, tot, c[N];
struct Splay{
    int rt, cnt, son[N][2], fa[N], sz[N], val[N];
    int rev[N], cov[N], sum[N], la[N], ra[N], ma[N];
    int top, rb[5000005];
    Splay(){
        rt = 0, cnt = 0, top = 0;
        fa[0] = son[0][0] = son[0][1] = sz[0] = rev[0] = cov[0] = 0;
        val[0] = sum[0] = la[0] = ra[0] = 0, ma[0] = -INF;
    }
    int new_node(int _val){
        int x = top ? rb[top--] : ++cnt;
        son[x][0] = son[x][1] = fa[x] = rev[x] = cov[x] = 0, sz[x] = 1;
        val[x] = ma[x] = sum[x] = _val, la[x] = ra[x] = std :: max(_val, 0);
        return x;
    }
    void recycle(int u){
        int ls = son[u][0], rs = son[u][1];
        if (ls) recycle(ls);
        if (rs) recycle(rs);
        rb[++top] = u;
    }
    void up(int u){
        int ls = son[u][0], rs = son[u][1];
        sz[u] = sz[ls] + sz[rs] + 1, sum[u] = sum[ls] + sum[rs] + val[u];
        la[u] = std :: max(la[ls], sum[ls] + val[u] + la[rs]);
        ra[u] = std :: max(ra[rs], sum[rs] + val[u] + ra[ls]);
        ma[u] = std :: max(std :: max(ma[ls], ma[rs]), ra[ls] + val[u] + la[rs]);
    }
    void down(int u){
        int ls = son[u][0], rs = son[u][1];
        if (cov[u]){
            if (ls) val[ls] = val[u], cov[ls] = 1, sum[ls] = sz[ls] * val[u];
            if (rs) val[rs] = val[u], cov[rs] = 1, sum[rs] = sz[rs] * val[u];
            if (val[u] > 0){
                if (ls) la[ls] = ra[ls] = ma[ls] = sum[ls];
                if (rs) la[rs] = ra[rs] = ma[rs] = sum[rs];
            }
            else{
                if (ls) la[ls] = ra[ls] = 0, ma[ls] = val[u];
                if (rs) la[rs] = ra[rs] = 0, ma[rs] = val[u];
            }
            cov[u] = 0;
        }
        if (rev[u]){
            if (ls) rev[ls] ^= 1, std :: swap(son[ls][0], son[ls][1]), std :: swap(la[ls], ra[ls]);
            if (rs) rev[rs] ^= 1, std :: swap(son[rs][0], son[rs][1]), std :: swap(la[rs], ra[rs]);
            rev[u] = 0;
        }
    }
    int dir(int x){ return son[fa[x]][1] == x; }
    void set(int x, int k, int y){ son[x][k] = y, fa[y] = x; }
    void rotate(int x){
        int y = fa[x], d = dir(x);
        set(fa[y], dir(y), x), set(y, d, son[x][!d]), set(x, !d, y);
        up(y), up(x);
    }
    void splay(int x, int g = 0){
        while (fa[x] != g){
            int y = fa[x];
            if (fa[y] != g) dir(y) == dir(x) ? rotate(y) : rotate(x);
            rotate(x);
        }
        if (!g) rt = x;
    }
    int build(int l, int r, int *a){
        if (l > r) return 0;
        if (l == r) return new_node(a[l]);
        int mid = (l + r) >> 1, u = new_node(a[mid]);
        son[u][0] = build(l, mid - 1, a), son[u][1] = build(mid + 1, r, a);
        fa[son[u][0]] = fa[son[u][1]] = u;
        return up(u), u;
    }
    int kth(int u, int k){
        down(u);
        int ls = son[u][0], rs = son[u][1];
        if (k == sz[ls] + 1) return u;
        else if (k <= sz[ls]) return kth(ls, k);
        else return kth(rs, k - sz[ls] - 1);
    }
    void insert(int x, int tot, int *a){
        int t = build(1, tot, a);
        int u = kth(rt, x); splay(u);
        int v = kth(rt, x + 1); splay(v, u);
        son[v][0] = t, fa[t] = v, up(v), up(u);
    }
    void erase(int l, int r){
        int u = kth(rt, l - 1); splay(u);
        int v = kth(rt, r + 1); splay(v, u);
        recycle(son[v][0]), son[v][0] = 0, up(v), up(u);
    }
    void cover(int l, int r, int c){
        int u = kth(rt, l - 1); splay(u);
        int v = kth(rt, r + 1); splay(v, u);
        int t = son[v][0];
        val[t] = c, cov[t] = 1, sum[t] = sz[t] * c;
        if (c > 0) la[t] = ra[t] = ma[t] = sum[t];
        else la[t] = ra[t] = 0, ma[t] = c;
        up(v), up(u);
    }
    void reverse(int l, int r){
        int u = kth(rt, l - 1); splay(u);
        int v = kth(rt, r + 1); splay(v, u);
        int t = son[v][0];
        rev[t] ^= 1, std :: swap(son[t][0], son[t][1]), std :: swap(la[t], ra[t]);
        up(v), up(u);
    }
    void query_sum(int l, int r){
        int u = kth(rt, l - 1); splay(u);
        int v = kth(rt, r + 1); splay(v, u);
        printf("%d\n", sum[son[v][0]]);
    }
    void query_max_sum(){ printf("%d\n", ma[rt]); }
}T;
int main(){
    n = read(), m = read(), n += 2, a[1] = a[n] = -INF;
    for (register int i = 2; i < n; ++i) a[i] = read(); // 整体右移
    T.rt = T.build(1, n, a);
    while (m--){
        scanf("%s", opt);
        if (opt[0] == 'M' && opt[2] == 'X') T.query_max_sum();
        else x = read() + 1, tot = read(); // +1是因为数组整体右移
        if (opt[0] == 'I'){
            for (register int i = 1; i <= tot; ++i) c[i] = read();
            T.insert(x, tot, c);
        }
        if (opt[0] == 'D') T.erase(x, x + tot - 1);
        if (opt[0] == 'M' && opt[2] == 'K') T.cover(x, x + tot - 1, read());
        if (opt[0] == 'R') T.reverse(x, x + tot - 1);
        if (opt[0] == 'G') T.query_sum(x, x + tot - 1);
    }
}

如发现代码有问题请在评论中指出，谢谢！

更新于：2020年3月26日

NOI

Splay

「模拟赛20190116 T2」序列

题意原题链接给定一个序列的前\(n\)项（\(a_0,a_1,a_2,\cdots,a_{n-1}\)），保证对于所有\(0\le i\le n-1\)，\(a_i\in \{n-1,n...

后缀数组学习笔记

后缀数组（Suffix Array, SA）是处理字符串的有力工具。它可以解决一些与字符串后缀LCP有关的问题。一些记号和约定在字符串\(S\)中，第\(i\)个字符到第\(j\...