题目描述

给出一个长度为 $n$ 的序列，进行 $m$ 次操作

• I p x 在 $p$ 处插入插入一个元素 $x$
• D p 删除 $p$ 处的一个元素
• R p x 修改 $p$ 处元素的值为 $x$
• Q l r 查询一个区间 $[l,r]$ 的最大子段和

$n, m \leq 10^5$

输入样例

5
3 -4 3 -1 6
10
I 6 2
Q 3 5
R 5 -4
Q 3 5
D 2
Q 1 5
I 2 -10
Q 1 6
R 2 -1
Q 1 6

输出样例

8
3
6
3
5

fhq_treap

主要还是为了存个板子，可以在 $log$ 的时间复杂度内对数组进行插入删除的那种

和 文艺平衡树 这道题一样
$split(u, k, x, y)$ 函数是指定一个 $k$，把 $u$ 树中的前 $k$ 个元素分给 $x$ 树，其余的分给 $y$ 树

维护区间最大子段和的操作和 这道题 差不多

注意本题中 $lmax, rmax$ 可以为 $0$
注意本平衡树模板如果没有子节点则会指向 $0$ 号节点，需要手动把 $0$ 号节点的最大子段和设为负无穷

时间复杂度 $O((n + m)log(n + m)$

C++ 代码

#include<cstdio>
#include<cstdlib>
#include<algorithm>

using namespace std;

const int N = 200010, INF = 0x3f3f3f3f;

struct Node{
    int l, r;
    int key, val, sz;
    int d, ld, rd, sum;
}tr[N];

int root, idx;

int get_node(int val)
{
    int u = ++ idx;
    tr[u].val = tr[u].d = tr[u].sum = val;
    tr[u].ld = tr[u].rd = max(0, val);
    tr[u].key = rand();
    tr[u].sz = 1;
    return u;
}

void pushup(int u)
{
    Node &left = tr[tr[u].l],  &right = tr[tr[u].r];
    tr[u].sz = left.sz + right.sz + 1;
    tr[u].sum = left.sum + right.sum + tr[u].val;
    tr[u].ld = max(left.ld, left.sum + tr[u].val + right.ld);
    tr[u].rd = max(right.rd, right.sum + tr[u].val + left.rd);
    tr[u].d = max(max(left.d, right.d), left.rd + tr[u].val + right.ld);
}

//  把 u 拆成 x, y两棵树，其中 x 的大小为 k 
void split(int u, int k, int &x, int &y)
{
    if(!u)  x = y = 0;
    else
    {
        if(tr[tr[u].l].sz < k)
        {
            x = u;
            split(tr[u].r, k - tr[tr[u].l].sz - 1, tr[u].r, y);
        }
        else
        {
            y = u;
            split(tr[u].l, k, x, tr[u].l);
        }
        pushup(u);
    }
}

int merge(int x, int y)
{
    if(!x or !y)  return x | y;
    if(tr[x].key > tr[y].key)
    {
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else
    {
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

int x, y, z;
void insert(int k, int val)
{
    split(root, k - 1, x, y);
    root = merge(merge(x, get_node(val)), y);
}

void dele(int k)
{
    split(root, k - 1, x, y);
    split(y, 1, y, z);
    root = merge(x, z);
}

void modify(int k, int val)
{
    split(root, k - 1, x, y);
    split(y, 1, y, z);
    tr[y].val = tr[y].d = tr[y].sum = val;
    tr[y].ld = tr[y].rd = max(0, val);
    root = merge(merge(x, y), z);
}

int query(int l, int r)
{
    split(root, l - 1, x, y);
    split(y, r - l + 1, y, z);
    int res = tr[y].d;
    root = merge(merge(x, y), z);
    return res;
}

int main()
{
    tr[0].d = -INF;

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        int x;
        scanf("%d", &x);
        root = merge(root, get_node(x));
    }

    int m;
    scanf("%d", &m);
    while(m --)
    {
        char op[2];
        int k, val, l, r;
        scanf("%s", op);
        if(op[0] == 'I')
        {
            scanf("%d%d", &k, &val);
            insert(k, val);
        }
        else if(op[0] == 'D')
        {
            scanf("%d", &k);
            dele(k);
        }
        else if(op[0] == 'R')
        {
            scanf("%d%d", &k, &val);
            modify(k, val);
        }
        else
        {
            scanf("%d%d", &l, &r);
            printf("%d\n", query(l, r));
        }
    }
    return 0;
}