Description

请写一个程序, 要求维护一个数列, 支持以下 \(6\) 种操作:

操作编号 输入文件中的格式 说明
1. 插入 INSERT posi tot c1 c2 ... ctot 在当前数列的第 \({pos}_i\) 个数字后插入 \(tot\) 个数字:\(c_1, c_2, \ldots, c_{tot}\); 若在数列首插入, 则 \({pos}_i\) 为 \(0\)
2. 删除 DELETE posi tot 从当前数列的第 \({pos}_i\) 个数字开始连续删除 \(tot\) 个数字
3. 修改 MAKE-SAME posi tot c 将当前数列的第 \({pos}_i\) 个数字开始的连续 \(tot\) 个数字统一修改为 \(c\)
4. 翻转 REVERSE posi tot 取出从当前数列的第 \({pos}_i\) 个数字开始的 \(tot\) 个数字, 翻转后放入原来的位置
5. 求和 GET-SUM posi tot 计算从当前数列开始的第 \({pos}_i\) 个数字开始的 \(tot\) 个数字的和并输出
6. 求和最大的子列 MAX-SUM 求出当前数列中和最大的一段子列, 并输出最大和

Input

输入文件的第 \(1\) 行包含两个数 \(n\) 和 \(m\),\(n\) 表示初始时数列中数的个数,\(m\) 表示 要进行的操作数目.

第 \(2\) 行包含 \(n\) 个数字, 描述初始时的数列.

以下 \(m\) 行, 每行一条命令, 格式参见问题描述中的表格.

Output

对于输入数据中的 GET-SUM 和 MAX-SUM 操作, 向输出文件依次打印结果, 每个答案 (数字) 占一行.

Sample Input

9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

Sample Output

-1
10
1
10

Data Range

你可以认为在任何时刻, 数列中至少有 \(1\) 个数.

输入数据一定是正确的, 即指定位置的数在数列中一定存在.

50% 的数据中, 任何时刻数列中最多含有 \(30000\) 个数;

100% 的数据中, 任何时刻数列中最多含有 \(500000\) 个数.

100% 的数据中, 任何时刻数列中任何一个数字均在 \([-1000, 1000]\) 内.

100% 的数据中,\(m \leq 20000\), 插入的数字总数不超过 \(4000000\) 个, 输入文件大小不超过 \(20\) MB.

Explanation

遇到这种看起来很像 SuperMemo 的题目就应该果断 Splay......

但是如果内存只有这么一点那么一定要垃圾回收, 毕竟开的点和删的点都会很多但是如果不 回收就会爆炸 QwQ

吐槽: 结果写了一遍带上垃圾回收无限 RE, 终于修好 GC 模块以后又开始无限 TLE...... 最终 在 Miloris 大神的指引下选择了用 NOI 的官方数据测评, 结果一个 AC 三个 TLE 两个 WA 剩下全是 RE......

于是开始了一个星期的紧张调试, 感觉自己突然变成了 Splayed By Trees

终于有一天把程序调出来了...... 首先 interval 就没写对, 合并好像有点问题; 其次 find 函数会莫名崩溃, 主要原因是没有在向下 traverse 的时候发 lazy; 再然后就是 MAX-SUM 本来是不应该写那么麻烦的, 直接询问 root 的大小就行了; 最后应该把两个端点的 val 值设成 \(-\infty\) 才对, 不然分分钟 WA.

所以说这锅并不该垃圾回收背......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
#define max_3(__x,__y,__z) max(max(__x,__y),__z)
using namespace std;
typedef long long lli;
const int maxn = 500100;
const lli infinit = 0x3f3f3f3f;

class SplayTree
{
public:
    int arr_i[maxn][6];
    #define ch(_x,_y) arr_i[_x][_y]
    #define lc(_x) arr_i[_x][0]
    #define rc(_x) arr_i[_x][1]
    #define par(_x) arr_i[_x][2]
    #define size(_x) arr_i[_x][3]
    #define lazymod(_x) arr_i[_x][4]
    #define lazyrev(_x) arr_i[_x][5]
    lli arr_l[maxn][6];
    #define val(_x) arr_l[_x][0]
    #define sum(_x) arr_l[_x][1]
    #define lmx(_x) arr_l[_x][2]
    #define mmx(_x) arr_l[_x][3]
    #define rmx(_x) arr_l[_x][4]
    #define lazyset(_x) arr_l[_x][5]
    int n, ncnt, root;
    queue<int> npool;
    int make_node(void)
    {
        int p = 0;
        if (!npool.empty()) {
            p = npool.front();
            npool.pop();
        } else {
            p = ++ncnt;
        }
        lc(p) = rc(p) = par(p) = 0;
        size(p) = 1;
        lazymod(p) = lazyrev(p) = false;
        val(p) = sum(p) = lmx(p) = mmx(p) = rmx(p) = 0ll;
        lazyset(p) = 0ll;
        return p;
    }
    void destroy_node(int p)
    {
        npool.push(p);
        return ;
    }
    void mark_mod(int p, lli v)
    {
        lazymod(p) = true;
        lazyset(p) = v;
        val(p) = v;
        sum(p) = size(p) * val(p);
        if (val(p) >= 0) {
            lmx(p) = mmx(p) = rmx(p) = sum(p);
        } else {
            lmx(p) = rmx(p) = 0;
            mmx(p) = val(p);
        }
        return ;
    }
    void mark_rev(int p)
    {
        lazyrev(p) ^= 1;
        swap(lc(p), rc(p));
        swap(lmx(p), rmx(p));
        return ;
    }
    void update_lazy(int p)
    {
        size(p) = size(lc(p)) + 1 + size(rc(p));
        sum(p) = sum(lc(p)) + val(p) + sum(rc(p));
        lmx(p) = max(lmx(lc(p)), sum(lc(p)) + val(p) + lmx(rc(p)));
        mmx(p) = max_3(mmx(lc(p)), rmx(lc(p)) + val(p) + lmx(rc(p)), mmx(rc(p)));
        rmx(p) = max(rmx(lc(p)) + val(p) + sum(rc(p)), rmx(rc(p)));
        return ;
    }
    void dispatch_lazy(int p)
    {
        if (lazymod(p)) {
            range(0, 1) if (ch(p, _))
                mark_mod(ch(p, _), val(p));
            lazymod(p) = lazyrev(p) = false;
        }
        if (lazyrev(p)) {
            range(0, 1) if (ch(p, _))
                mark_rev(ch(p, _));
            lazyrev(p) = false;
        }
        return ;
    }
    void rotate(int p)
    {
        int q = par(p), g = par(q);
        int x = p == rc(q), y = q == rc(g);
        dispatch_lazy(q);
        dispatch_lazy(p);
        ch(q, x) = ch(p, !x); if (ch(q, x)) par(ch(q, x)) = q;
        ch(p, !x) = q; par(q) = p;
        if (g) ch(g, y) = p; par(p) = g;
        update_lazy(q);
        update_lazy(p);
        return ;
    }
    void splay(int p, int t = 0)
    {
        for (int q = 0; (q = par(p)) && q != t; rotate(p))
            if (par(q) && par(q) != t)
                rotate((p == lc(q)) == (q == lc(par(q))) ? q : p);
        if (t == 0) root = p;
        return ;
    }
    int find(int x)
    {
        int p = root;
        while (p) {
            dispatch_lazy(p);
            if (x <= size(lc(p))) {
                p = lc(p);
                continue;
            } x -= size(lc(p));
            if (x <= 1) {
                return p;
            } x -= 1;
            p = rc(p);
        }
        return p;
    }
    int build_tree(int l, int r, lli arr[])
    {
        if (l > r) return 0;
        // So unless it's null node, we assume it's correct
        int p = make_node();
        int mid = (l + r) >> 1;
        val(p) = arr[mid];
        lc(p) = build_tree(l, mid - 1, arr);
        rc(p) = build_tree(mid + 1, r, arr);
        range(0, 1) if (ch(p, _)) par(ch(p, _)) = p;
        update_lazy(p);
        return p;
    }
    void insert(int pos, int n, lli arr[])
    {
        int lp = find(pos + 1), rp = find(pos + 2);
        splay(lp, 0);
        splay(rp, root);
        int np = build_tree(1, n, arr);
        lc(rp) = np;
        par(np) = rp;
        splay(np, 0);
        this->n += n;
        return ;
    }
    void remove(int l, int r)
    {
        int lp = find(l), rp = find(r + 2);
        splay(lp, 0);
        splay(rp, root);
        // Recycling subtree
        queue<int> que;
        que.push(lc(rp));
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            range(0, 1) if (ch(p, _))
                que.push(ch(p, _));
            destroy_node(p);
        }
        // Disconnecting
        lc(rp) = 0;
        splay(rp, 0);
        this->n -= r - l + 1;
        return ;
    }
    void change(int l, int r, lli val)
    {
        int lp = find(l), rp = find(r + 2);
        splay(lp, 0);
        splay(rp, root);
        mark_mod(lc(rp), val);
        splay(lc(rp), 0);
        return ;
    }
    void reverse(int l, int r)
    {
        int lp = find(l), rp = find(r + 2);
        splay(lp, 0);
        splay(rp, root);
        mark_rev(lc(rp));
        splay(lc(rp), 0);
        return ;
    }
    lli get_sum(int l, int r)
    {
        int lp = find(l), rp = find(r + 2);
        splay(lp, 0);
        splay(rp, root);
        lli res = sum(lc(rp));
        return res;
    }
    int get_max_sum(void)
    {
        return mmx(root);
    }
    void init(void)
    {
        this->n = 0;
        this->ncnt = 0;
        while (!npool.empty())
            npool.pop();
        this->root = make_node();
        rc(root) = make_node();
        par(rc(root)) = root;
        size(root) += 1;
        mmx(0) = val(root) = val(rc(root)) = -infinit;
        splay(rc(root), 0);
        return ;
    }
} st;

int n, m;
lli arr[maxn];
char str[64];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    st.init();
    st.insert(0, n, arr);
    for (int idx = 1; idx <= m; idx++) {
        scanf("%s", str);
        if (str[0] == 'I') {
            int pos, tot; scanf("%d%d", &pos, &tot);
            for (int i = 1; i <= tot; i++)
                scanf("%lld", &arr[i]);
            st.insert(pos, tot, arr);
        } else if (str[0] == 'D') {
            int pos, tot; scanf("%d%d", &pos, &tot);
            st.remove(pos, pos + tot - 1);
        } else if (str[0] == 'M' && str[2] == 'K') {
            int pos, tot, v; scanf("%d%d%d", &pos, &tot, &v);
            st.change(pos, pos + tot - 1, v);
        } else if (str[0] == 'R') {
            int pos, tot; scanf("%d%d", &pos, &tot);
            st.reverse(pos, pos + tot - 1);
        } else if (str[0] == 'G') {
            int pos, tot; scanf("%d%d", &pos, &tot);
            lli res = st.get_sum(pos, pos + tot - 1);
            printf("%lld\n", res);
        } else if (str[0] == 'M' && str[2] == 'X') {
            lli res = st.get_max_sum();
            printf("%lld\n", res);
        }
    }
    return 0;
}