题解：维护数列

一、题目分析

本题要求编写程序维护一个数列，支持插入、删除、修改、翻转、求和以及求最大子列和这6种操作。输入包含初始数列和一系列操作指令，需要根据操作要求输出相应结果。

二、解题思路

本题使用Splay树来实现对数列的维护。Splay树是一种自平衡二叉搜索树，通过旋转操作保持树的平衡，同时利用其性质来高效地实现各种操作。

（一）数据结构定义

struct Node
{
    int s[2], p, v;
    int rev, same;
    int size, sum, ms, ls, rs;

    void init(int _v, int _p)
    {
        s[0] = s[1] = 0, p = _p, v = _v;
        rev = same = 0;
        size = 1, sum = ms = v;
        ls = rs = max(v, 0);
    }
}tr[N];

定义节点结构体Node，包含以下成员：
- s[2]：左右子节点指针。
- p：父节点指针。
- v：节点值，即数列中的数字。
- rev：翻转标记，用于翻转操作。
- same：统一修改标记，用于修改操作。
- size：子树大小。
- sum：子树节点值之和。
- ms：子树中最大子列和。
- ls：从子树最左边开始的最大子列和。
- rs：从子树最右边开始的最大子列和。

init函数用于初始化节点。

（二）Splay树基本操作函数

1. 更新节点信息函数pushup：

void pushup(int x)
{
    auto &u = tr[x], &l = tr[u.s[0]], &r = tr[u.s[1]];
    u.size = l.size + r.size + 1;
    u.sum = l.sum + r.sum + u.v;
    u.ls = max(l.ls, l.sum + u.v + r.ls);
    u.rs = max(r.rs, r.sum + u.v + l.rs);
    u.ms = max(max(l.ms, r.ms), l.rs + u.v + r.ls);
}

根据左右子树的信息更新当前节点的子树大小、节点值之和、从左边开始的最大子列和、从右边开始的最大子列和以及子树中的最大子列和。

1. 下传标记函数pushdown：

void pushdown(int x)
{
    auto &u = tr[x], &l = tr[u.s[0]], &r = tr[u.s[1]];
    if (u.same)
    {
        u.same = u.rev = 0;
        if (u.s[0]) l.same = 1, l.v = u.v, l.sum = l.v * l.size;
        if (u.s[1]) r.same = 1, r.v = u.v, r.sum = r.v * r.size;
        if (u.v > 0)
        {
            if (u.s[0]) l.ms = l.ls = l.rs = l.sum;
            if (u.s[1]) r.ms = r.ls = r.rs = r.sum;
        }
        else
        {
            if (u.s[0]) l.ms = l.v, l.ls = l.rs = 0;
            if (u.s[1]) r.ms = r.v, r.ls = r.rs = 0;
        }
    }
    else if (u.rev)
    {
        u.rev = 0, l.rev ^= 1, r.rev ^= 1;
        swap(l.ls, l.rs), swap(r.ls, r.rs);
        swap(l.s[0], l.s[1]), swap(r.s[0], r.s[1]);
    }
}

将节点的修改标记和翻转标记下传给左右子节点，并更新子节点的相关信息。

1. 旋转函数rotate：

void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

对节点x进行旋转操作，根据x是其父节点y的左儿子还是右儿子，进行相应的旋转，并更新节点信息。

1. Splay操作函数splay：

void splay(int x, int k)
{
    while (tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if (!k) root = x;
}

将节点x通过旋转操作调整到节点k的子节点位置（若k = 0，则调整到根节点）。

1. 获取第k个节点函数get_k：

int get_k(int k)
{
    int u = root;
    while (u)
    {
        pushdown(u);
        if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].size + 1 == k) return u;
        else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }
}

在Splay树中找到第k个节点，通过比较左子树大小和k的值，在树中进行搜索。

（三）辅助函数

1. 构建Splay树函数build：

int build(int l, int r, int p)
{
    int mid = l + r >> 1;
    int u = nodes[tt -- ];
    tr[u].init(w[mid], p);
    if (l < mid) tr[u].s[0] = build(l, mid - 1, u);
    if (mid < r) tr[u].s[1] = build(mid + 1, r, u);
    pushup(u);
    return u;
}

通过递归方式构建Splay树，返回根节点。

1. 回收节点函数dfs：

void dfs(int u)
{
    if (tr[u].s[0]) dfs(tr[u].s[0]);
    if (tr[u].s[1]) dfs(tr[u].s[1]);
    nodes[ ++ tt] = u;
}

通过深度优先搜索回收Splay树中的节点。

（四）主函数main

int main()
{
    for (int i = 1; i < N; i ++ ) nodes[ ++ tt] = i;
    scanf("%d%d", &n, &m);
    tr[0].ms = w[0] = w[n + 1] = -INF;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    root = build(0, n + 1, 0);

    char op[20];
    while (m -- )
    {
        scanf("%s", op);
        if (!strcmp(op, "INSERT"))
        {
            int posi, tot;
            scanf("%d%d", &posi, &tot);
            for (int i = 0; i < tot; i ++ ) scanf("%d", &w[i]);
            int l = get_k(posi + 1), r = get_k(posi + 2);
            splay(l, 0), splay(r, l);
            int u = build(0, tot - 1, r);
            tr[r].s[0] = u;
            pushup(r), pushup(l);
        }
        else if (!strcmp(op, "DELETE"))
        {
            int posi, tot;
            scanf("%d%d", &posi, &tot);
            int l = get_k(posi), r = get_k(posi + tot + 1);
            splay(l, 0), splay(r, l);
            dfs(tr[r].s[0]);
            tr[r].s[0] = 0;
            pushup(r), pushup(l);
        }
        else if (!strcmp(op, "MAKE-SAME"))
        {
            int posi, tot, c;
            scanf("%d%d%d", &posi, &tot, &c);
            int l = get_k(posi), r = get_k(posi + tot + 1);
            splay(l, 0), splay(r, l);
            auto& son = tr[tr[r].s[0]];
            son.same = 1, son.v = c, son.sum = c * son.size;
            if (c > 0) son.ms = son.ls = son.rs = son.sum;
            else son.ms = c, son.ls = son.rs = 0;
            pushup(r), pushup(l);
        }
        else if (!strcmp(op, "REVERSE"))
        {
            int posi, tot;
            scanf("%d%d", &posi, &tot);
            int l = get_k(posi), r = get_k(posi + tot + 1);
            splay(l, 0), splay(r, l);
            auto& son = tr[tr[r].s[0]];
            son.rev ^= 1;
            swap(son.ls, son.rs);
            swap(son.s[0], son.s[1]);
            pushup(r), pushup(l);
        }
        else if (!strcmp(op, "GET-SUM"))
        {
            int posi, tot;
            scanf("%d%d", &posi, &tot);
            int l = get_k(posi), r = get_k(posi + tot + 1);
            splay(l, 0), splay(r, l);
            printf("%d\n", tr[tr[r].s[0]].sum);
        }
        else printf("%d\n", tr[root].ms);
    }

    return 0;
}

1. 初始化节点池nodes，读取初始数列的长度n和操作次数m，设置边界值，读取初始数列并构建Splay树。
2. 循环处理每个操作：
   • 插入操作（INSERT）：获取插入位置前后的节点，将它们Splay到合适位置，构建新的子树并插入到Splay树中。
   • 删除操作（DELETE）：获取删除位置前后的节点，将它们Splay到合适位置，回收要删除的子树节点并更新Splay树。
   • 修改操作（MAKE-SAME）：获取修改位置前后的节点，将它们Splay到合适位置，下传修改标记并更新相关信息。
   • 翻转操作（REVERSE）：获取翻转位置前后的节点，将它们Splay到合适位置，下传翻转标记并更新相关信息。
   • 求和操作（GET-SUM）：获取求和位置前后的节点，将它们Splay到合适位置，输出指定子树的节点值之和。
   • 求最大子列和操作（MAX-SUM）：输出Splay树根节点的最大子列和。

四、时间复杂度和空间复杂度

（一）时间复杂度

• Splay树基本操作：插入、删除、旋转、Splay操作和获取第k个节点等操作的时间复杂度均为(O(\log n))，其中n为Splay树中节点的数量。
• 每个操作：每个操作都需要先找到相关节点并进行Splay操作，所以每个操作的时间复杂度为(O(\log n))。
• 总的时间复杂度为(O(m\log n))，其中m为操作的总数。

（二）空间复杂度

Splay树最多存储n个节点，节点池nodes大小为N，所以空间复杂度为(O(N))，近似为(O(n))。