AcWing 266. 超级备忘录    原题链接    困难

作者： 作者的头像   Clever_Jimmy ,  2020-01-25 22:48:17 ,  所有人可见 ,  阅读 2037

8


2

题目描述

给定一个序列 $A$，要求支持以下操作：

  1. $\text{ADD}(l, r, val)$

    将 $A[l \cdots r]$ 全部加上一个数 $val$；

  2. $\text{REVERSE}(l, r)$

    将 $A[l \cdots r]$ 逆序排布；

  3. $\text{REVOLVE}(l, r, T)$

    将 $A[l, r - T]$ 移至 $A[r - T + 1, r]$ 后面；

  4. $\text{INSERT}(x, val)$

    在 $A_x$ 后面插入 $val$；

  5. $\text{DELETE}(x)$

    删除 $A_x$ 这个元素；

  6. $\text{MIN}(l, r)$

    求 $\min\limits_{j = l}^rA_j$。

样例输入

7
9 8 7 1 1 1 9 
9
ADD 1 6 10
ADD 2 7 7
REVERSE 1 7
MIN 1 3
REVOLVE 1 6 5
DELETE 7
MIN 1 5
MIN 2 5
MIN 1 4

样例输出

16
18
18
18

思路

这一题，看到了序列翻转的操作，自然地可以想到用 $\text{Splay}$ 来解决。

定义1：一棵树根节点的右节点的左结点为这棵树的 重要点。

定义2：一棵树通过最右下方的点为这棵树的 极值点。

  1. $\text{ADD}(l, r, val)$ 操作

    我们先将 $[l, r]$ 这个区间 $\text{split}$ 出来，然后在这个区间上打上标记即可。

    注意标记的意义：这个点的权值已经被修改过，但是它的子树没有被修改。

  2. $\text{REVERSE}(l, r)$ 操作

    同 (1) 一样先将 $[l, r]$ 这个区间 $\text{split}$ 出来，然后在这个区间上打上标记。

  3. $\text{REVOLVE}(l, r, T)$ 操作

    容易想到的是，轮换 $r - l + 1$ 次是没有意义的。于是我们先将 $T$ 对 $r - l + 1$ 取模，再进行操作。

    1. 先将 $[l, r - T]$ 这个区间 $\text{split}$ 出来（得到 $f_1$）

      我们把它从 $\text{splay}$ 中删去。

      注意到此时我们应该将这个区间从 $root$ 的左儿子中取出。

    2. 再将 $[r - T + 1, r]$ 这个区间 $\text{split}$ 出来（得到 $f_3$）

      • 若 $f_3$ 为空，记 $f_4$ 为根节点的右儿子的右儿子。

        显然我们应如 $root-f_1-f_4$ 连接这三个点。

        我们先考虑将 $f_1$ 连接到 $root$ 上。

        然后记这棵树的极值点为 $f_5$，我们将 $f_5$ 伸展至根的右孩子。

        可以证明，此时 $f_5$ 无右孩子，于是我们可以将 $f_4$ 连接到 $f_5$ 上。

      • 若 $f_3$ 不为空，那么我们找到这棵树的极值点，将它伸展至重要点。

        可以证明，此时 $f_3$ 无右孩子，于是我们可以将 $f_1$ 连接到 $f_3$ 上。

    值得注意的是，这个操作带来的标记的上传以及下放是十分麻烦的。

  4. $\text{INSERT}(x, val)$ 操作

    我们将 $[x, x]$ 这个区间 $\text{split}$ 出来，设这个点为 $p$。

    将 $val$ 作为右孩子连接到 $p$ 上即可。

  5. $\text{DELETE}(x)$ 操作

    这个操作比较简单，直接将 $[x, x]$ 这个区间 $\text{split}$ 出来，并将其父亲的左孩子置为空即可。

  6. $\text{MIN}(l, r)$ 操作

    我们将 $[l, r]$ 这个区间 $\text{split}$ 出来，设这个点为 $p$。

    输出 $p$ 的子树中的最小值即可。

代码实现

#include <bits/stdc++.h>
#define LL long long
#define rgi register int
#define rgl register long long
#define il inline

const LL oo = 0x3f3f3f3f3f3f3f3fLL;
const int N = 2e6 + 10;

int n, m;
LL a[N];

il int read() {
    rgi x = 0, f = 0, ch;
    while(!isdigit(ch = getchar())) f |= ch == '-';
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

struct SPLAYNODE {
    int fa, ch[2], siz, rev;
    LL val, min_val, add;
};

struct SPLAY {
    static const int MAXSIZE = N;
    int root, cntNode; SPLAYNODE t[MAXSIZE];

    int son(int p) { return p == t[t[p].fa].ch[1]; }
    int make(int f, int v) {
        t[++cntNode].fa = f;
        t[cntNode].val = t[cntNode].min_val = v;
        t[cntNode].siz = 1, t[cntNode].rev = t[cntNode].add = 0;
        return cntNode;
    }
    void connect(int p, int f, int o) {  t[p].fa = f, t[f].ch[o] = p; }
    void pushup(int p) {
        t[p].min_val = t[p].val;
        if(t[p].ch[0]) t[p].min_val = std::min(t[p].min_val, t[t[p].ch[0]].min_val);
        if(t[p].ch[1]) t[p].min_val = std::min(t[p].min_val, t[t[p].ch[1]].min_val);
        t[p].siz = t[t[p].ch[0]].siz + t[t[p].ch[1]].siz + 1;
    }
    void pushdown(int p) {
        if(t[p].rev) {
            std::swap(t[p].ch[0], t[p].ch[1]);
            t[t[p].ch[0]].rev ^= 1;
            t[t[p].ch[1]].rev ^= 1;
            t[p].rev = 0;
        }
        if(t[p].add) {
            SPLAYNODE &L = t[t[p].ch[0]], &R = t[t[p].ch[1]]; LL v = t[p].add;
            if(t[p].ch[0]) L.add += v, L.val += v, L.min_val += v;
            if(t[p].ch[1]) R.add += v, R.val += v, R.min_val += v;
            t[p].add = 0;
        }
    }

    void rotate(int p) {
        int f = t[p].fa, g = t[f].fa;
        int o1 = son(p), o2 = son(f);
        connect(t[p].ch[o1 ^ 1], f, o1);
        connect(f, p, o1 ^ 1);
        connect(p, g, o2);
        pushup(f), pushup(p);
    }
    void splay(int p, int tmp) {
        int tar = t[tmp].fa;
        while(t[p].fa != tar) {
            int f = t[p].fa, g = t[f].fa;
            if(g != tar) son(p) ^ son(f) ? rotate(p) : rotate(f);
            rotate(p);
        }
        if(tmp == root) root = p;
    }

    void build(int &p, int f, int l, int r) {
        if(l > r) return;
        p = ++cntNode;
        int mid = l + r >> 1;
        t[p].fa = f, t[p].val = t[p].min_val = a[mid], t[p].rev = t[p].add = 0;
        build(t[p].ch[0], p, l, mid - 1);
        build(t[p].ch[1], p, mid + 1, r);
        pushup(p);
    }
    int kth(int rk) {
        int p = root;
        while(1) {
            pushdown(p);
            if(t[t[p].ch[0]].siz >= rk) p = t[p].ch[0];
            else {
                rk -= t[t[p].ch[0]].siz + 1;
                if(!rk) return p;
                p = t[p].ch[1];
            }
        }
    }
    int split(int l, int r, int dir) { // dir = 1 ->make it to the right
        int nxt[2] = { kth(l), kth(r + 2) };
        splay(nxt[dir ^ 1], root);
        splay(nxt[dir], t[root].ch[dir]);
        return t[t[root].ch[dir]].ch[dir ^ 1];
    }
    void revolve(int l, int r, int d) {
        if(!d) return;
        int f1 = split(l, r - d, 0);
        int f2 = t[root].ch[0];
        pushdown(root), pushdown(f2);
        t[f2].ch[1] = 0;
        pushup(f2), pushup(root);
        int f3 = split(r - d + 1 - t[f1].siz, r - t[f1].siz, 1);
        if(!f3) {
            int f4 = t[t[root].ch[1]].ch[1];
            connect(f1, t[root].ch[1], 1);
            pushup(t[root].ch[1]), pushup(root);
            int f5 = root; pushdown(root);
            while(t[f5].ch[1]) f5 = t[f5].ch[1], pushdown(f5);
            splay(f5, t[root].ch[1]);
            pushdown(root), pushdown(f5);
            connect(f4, f5, 1);
            pushup(t[root].ch[1]), pushup(root);
        }
        else {
            pushdown(f3);
            while(t[f3].ch[1]) f3 = t[f3].ch[1], pushdown(f3);
            splay(f3, t[t[root].ch[1]].ch[0]);
            connect(f1, t[t[root].ch[1]].ch[0], 1);
            pushup(t[t[root].ch[1]].ch[0]), pushup(t[root].ch[1]), pushup(root);
        }
    }
} T;

int main() {
    n = read();
    for(rgi i = 1; i <= n; ++i) a[i + 1] = read();
    T.t[0].min_val = a[0] = a[n + 2] = oo;
    T.build(T.root, 0, 1, n + 2);
    m = read();
    for(rgi i = 1; i <= m; ++i) {
        std::string opt; std::cin >> opt;
        if(opt == "ADD") {
            int l = read(), r = read(), v = read();
            int p = T.split(l, r, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.t[p].add += v;
            T.t[p].val += v;
            T.t[p].min_val += v;
            T.pushup(f), T.pushup(g);
        }
        if(opt == "REVERSE") {
            int l = read(), r = read();
            int p = T.split(l, r, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.t[p].rev ^= 1;
        }
        if(opt == "REVOLVE") {
            int l = read(), r = read(), d = read();
            d %= r - l + 1;
            T.revolve(l, r, d);
        }
        if(opt == "INSERT") {
            int x = read(), v = read();
            int p = T.split(x, x, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.pushdown(p);
            T.t[p].ch[1] = T.make(p, v);
            T.pushup(p), T.pushup(f), T.pushup(g);
        }
        if(opt == "DELETE") {
            int x = read();
            int p = T.split(x, x, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.t[f].ch[0] = 0;
            T.pushup(f), T.pushup(g);
        }
        if(opt == "MIN") {
            int l = read(), r = read();
            int p = T.split(l, r, 1);
            printf("%lld\n", T.t[p].min_val);
        }
    }
    return 0;
}

有任何疑问请在评论区留言，也可 QQ 私聊。

QQ : 506503360

7 评论

用户头像
pengyule   2021-02-27 12:02         踩      回复

非常感谢

用户头像
CLB   2020-08-18 15:27         踩      回复

请问rotate中不用判断儿子是否存在吗？

用户头像
Clever_Jimmy   2020-08-18 16:14         踩      回复

rotate 中为啥要判断「儿子」是否存在啊？
请问我能认为「儿子」是指「p 的儿子」吗？
我是将 p 旋转到上面去，与 p 的儿子无关吧……
毕竟空的就是空的。

用户头像
Clever_Jimmy   2020-08-18 16:15         踩      回复

（我从来没判过）

用户头像
吴地文笔   2020-03-16 10:05         踩      回复

谢谢提供这么优质的分享。有个疑问：revolve中，右半分离出来的f3怎么可能是空的？如果需要轮换长度d为0，就不用操作了，其余情况右半都是有元素的，所以f3不可能为空啊？

用户头像
吴地文笔   2020-03-16 20:16         踩      回复

我试了，不需要考虑f4和f5，已经AC了

用户头像
Clever_Jimmy   2020-08-13 16:42         踩      回复

多谢指正！