Loi_Vampire's Blog

自己选择的路，就算跪着也要走完

02/1
19:52
数据结构 线段树

GSS3 - Can you answer these queries III 线段树-最大连续子段和

无回复 109 views

You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations: modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

Input

The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN. The third line contains an integer M. The next M lines contain the operations in following form: 0 x y: modify Ax into y (|y|<=10000). 1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

Output

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

Example

Input:
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3

Output:
6
4
-3

 

还是最大连续子段和，只是加了修改操作，同GSS1

View Code
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdio>
#include <algorithm>
#define lson (now << 1)
#define rson (now << 1 | 1)
using namespace std;
typedef long long LL;
const int SZ = 5e4 + 10;
 
struct SGT
{
    int l, r;
    LL sum, lmax, rmax, allmax;
}tree[SZ * 4];
int num[SZ];
 
void read(int &num)
{
    num = 0;
    char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while('0' <= c && c <= '9') {num = num * 10 + (c - '0'); c = getchar();}
    num *= f;
}
 
void update(int now)
{
    tree[now].sum = tree[lson].sum + tree[rson].sum;
    tree[now].lmax = max(tree[lson].lmax, tree[lson].sum + tree[rson].lmax);
    tree[now].rmax = max(tree[rson].rmax, tree[rson].sum + tree[lson].rmax);
    tree[now].allmax = max(tree[lson].rmax + tree[rson].lmax, max(tree[lson].allmax, tree[rson].allmax));
}
 
void build(int now, int l, int r)
{
    tree[now].l = l;
    tree[now].r = r;
    if(l == r)
    {
        tree[now].sum = tree[now].lmax = tree[now].rmax = tree[now].allmax = num[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    update(now);    
}
 
void change(int now, int pos, int value)
{
    if(tree[now].l == tree[now].r)
    {
        tree[now].sum = tree[now].lmax = tree[now].rmax = tree[now].allmax = value;
        return ;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(pos <= mid) change(lson, pos, value);
    else change(rson, pos, value);
    update(now);
}
 
SGT ask(int now, int l, int r)
{
    if(l == tree[now].l && tree[now].r == r)
        return tree[now];
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(r <= mid) return ask(lson, l, r);
    if(l > mid) return ask(rson, l, r);
    SGT AskL = ask(lson, l, mid), AskR = ask(rson, mid + 1, r);
    SGT ans;
    ans.sum = AskL.sum + AskR.sum;
    ans.lmax = max(AskL.lmax, AskL.sum + AskR.lmax);
    ans.rmax = max(AskR.rmax, AskR.sum + AskL.rmax);
    ans.allmax = max(AskL.rmax + AskR.lmax, max(AskL.allmax, AskR.allmax));
    return ans;
}
 
int main()
{
    int n, m;
    read(n);
    for(int i = 1; i <= n; i++)
        read(num[i]);
    build(1, 1, n);
    read(m);
    int op, a, b;
    while(m--)
    {
        read(op), read(a), read(b);
        if(!op) change(1, a, b);
        else printf("%lld\n", ask(1, a, b).allmax);
    }
    return 0;
}