GSS3-Can you answer these queries III

Description

You are given a sequence \(a\) of \(n\) integers between \(-10000\) and \(10000\). On this sequence you have to apply \(m\) operations:

  • Modify the \(i-th\) element in the sequence.
  • For given \(x, y\), print \(max\{a_i + a_{i+1} + \ldots + a_j | x \leq i \leq j \leq y\}\).

Input

The first line of input contains an integer \(n\).

The following line contains \(n\) integers, representing the sequence \(a_1 \ldots a_n\).

The third line contains an integer \(m\). The next \(m\) lines contain the operations in following form:

  • 0 x y: Modify \(a_x\) into \(y\) (\(|y| \leq 10000\)) .
  • 1 x y: Print \(max\{a_i + a_{i+1} + \ldots + a_j | x \leq i \leq j \leq y\}\).

Output

For each query, print an integer as the problem required.

Sample Input

4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3

Sample Output

6
4
-3

Data Range

All data are guaranteed that:\(n \leq 50000, m \leq 50000, -10000 \leq a_i \leq 10000\).

Explanation

维护一棵线段树区间从左边开始的最大和和从右边开始的最大和和从中间开始的最大和. 这些数据可以 \(O(1)\) 合并, 相比 GSS1 来说只是多了修改. 所以需要加一个 lazy 来维护批量修改操作.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 50010;

struct interval {
    lli maxx, lmx, mmx, rmx, sum;
    interval(void) {
        maxx = lmx = mmx = rmx = sum = 0; }
    interval(lli v) {
        maxx = sum = v; lmx = mmx = rmx = v > 0 ? v : 0; }
    interval(lli a, lli b, lli c, lli d, lli e) {
        maxx = a; lmx = b, mmx = c, rmx = d; sum = e; }
}; interval join(interval a, interval b) {
    interval c; c.maxx = max(a.maxx, b.maxx);
    c.lmx = max(a.lmx, a.sum + b.lmx);
    c.rmx = max(b.rmx, b.sum + a.rmx);
    c.mmx = max(max(a.mmx, b.mmx), a.rmx + b.lmx);
    c.sum = a.sum + b.sum;
    return c;
}

class SegmentTree
{
public:
    struct node
    {
        node *lc, *rc;
        int lb, mb, rb;
        interval val;
    } *root, npool[maxn<<1];
    int n, ncnt;
    node* make_node(void)
    {
        node *p = &npool[++ncnt];
        p->lc = p->rc = NULL;
        p->lb = p->mb = p->rb = 0;
        p->val = 0;
        return p;
    }
    interval query(node *p, int l, int r)
    {
        if (p->lb == l && p->rb == r) {
            return p->val;
        }
        if (r <= p->mb) {
            return query(p->lc, l, r);
        } else if (l > p->mb) {
            return query(p->rc, l, r);
        } else {
            return join(query(p->lc, l, p->mb),
                query(p->rc, p->mb + 1, r));
        }
        return interval();
    }
    lli query(int l, int r)
    {
        if (l > r) swap(l, r);
        interval res = this->query(root, l, r);
        if (res.maxx < 0) return res.maxx;
        return res.mmx;
    }
    void change(node *p, int pos, lli val)
    {
        if (p->lb == p->rb) {
            p->val = interval(val);
            return ;
        }
        if (pos <= p->mb)
            change(p->lc, pos, val);
        else if (pos > p->mb)
            change(p->rc, pos, val);
        p->val = join(p->lc->val, p->rc->val);
        return ;
    }
    void change(int pos, lli val)
    {
        this->change(root, pos, val);
    }
    node* build_tree(int l, int r, lli arr[])
    {
        node *p = make_node();
        int mid = (l + r) >> 1;
        p->lb = l; p->mb = mid; p->rb = r;
        if (p->lb == p->rb) {
            p->val = interval(arr[mid]);
        } else {
            p->lc = build_tree(l, mid, arr);
            p->rc = build_tree(mid + 1, r, arr);
            p->val = join(p->lc->val, p->rc->val);
        }
        return p;
    }
    void build(int n, lli arr[])
    {
        this->n = n;
        this->root = this->build_tree(1, n, arr);
        return ;
    }
} st;

int n, m;
lli arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    st.build(n, arr);
    // Can you answer these queries
    scanf("%d", &m);
    for (int i = 1, x, l, r; i <= m; i++) {
        scanf("%d%d%d", &x, &l, &r);
        if (x == 1) {
            lli res = st.query(l, r);
            printf("%lld\n", res);
        } else if (x == 0) {
            st.change(l, r);
        }
    }
    return 0;
}