「SPOJ 1716」GSS3 - Can you answer these queries III

Description

给定一个长度为 $n\ (n \leq 50000, \mid a_i \mid \leq 10000)$ 的整数序列 和 $m\ (m \leq 50000)$ 个操作（操作有 $2$ 种）：

0 x y：把 $a_x\ (1 \leq x \leq n)$ 的值修改为 $y\ (\mid y \mid \leq 10000)$。

1 x y： 询问区间 $[x,y]\ (1 \leq x \leq y \leq n)$ 的最大子段和。

Source

[Luogu]SP1716

[SPOJ]GSS3

Solution

前置知识：

线段树

仅仅是比 「SPOJ1043」GSS1 多了一个单点修改操作，暴力修改并且加上 $\mathrm{pushUp}$ 操作即可。

$\mathrm{pushUp}$ 操作 和 $\mathrm{query}$ 操作 的详细实现过程请看上一行链接。

Code

复制

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 5e4 + 10;
int n, q, l, r;
bool opt;
LL a[MAXN];
struct SegmentTree {
    struct Node {
        LL sum, lsum, rsum, res;
    } seg[MAXN << 2];
    
    inline int lson(int x) {
        return x << 1;
    }
    inline int rson(int x) {
        return x << 1 | 1;
    }
    inline Node merge(Node x, Node y) {
        Node now;
        now.sum = x.sum + y.sum;
        now.res = max(max(x.res, y.res), x.rsum + y.lsum);
        now.lsum = max(x.lsum, x.sum + y.lsum);
        now.rsum = max(y.rsum, x.rsum + y.sum);
        return now;
    }
    inline void pushUp(int x) {
        seg[x] = merge(seg[lson(x)], seg[rson(x)]);
    }
    void build(int x, int l, int r, LL *a) {
        if (l == r) {
            seg[x] = (Node) { a[l], a[l], a[l], a[l] };
            return;
        }
        int mid = (l + r) >> 1;
        build(lson(x), l, mid, a), build(rson(x), mid + 1, r, a);
        pushUp(x);
    }
    void update(int q, int l, int r, int x, LL p) {
        if (l == r) {
            seg[x] = (Node) { p, p, p, p };
            return;
        }
        int mid = (l + r) >> 1;
        if (q <= mid) update(q, l, mid, lson(x), p);
        else update(q, mid + 1, r, rson(x), p);
        pushUp(x);
    }
    Node query(int ql, int qr, int l, int r, int x) {//分成 3 种情况考虑
        if (ql <= l && qr >= r) return seg[x];
        int mid = (l + r) >> 1;
        if (qr <= mid) return query(ql, qr, l, mid, lson(x));
        if (ql > mid) return query(ql, qr, mid + 1, r, rson(x));
        return merge(query(ql, qr, l, mid, lson(x)), 
        query(ql, qr, mid + 1, r, rson(x)));
    }
} tr;

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    tr.build(1, 1, n, a);
    for (read(q); q; --q) {
        read(opt), read(l), read(r);
        if (!opt) tr.update(l, 1, n, 1, r);
        else {
            write(tr.query(l, r, 1, n, 1).res);
            putchar('\n');
        }
    }
    return 0;
}