Talk is Cheap, Show Me the Code!

0%

动态区间连续和

Posted on In

给定一个长度为n的序列A，有m次操作，每次操作为以下两种之一：

（1）0 x a，把A[x]改成a。

（2）1 x y，求区间[x,y]的最大连续和，即 max{A[i] + … + A[j]} (x<=i<=j<=y)

输入描述:

第一行一个整数n。
第二行n个元素，表示序列中的元素。
第三行一个整数m，表示操作的个数。
接下来m行，每行为两种操作中的一种。

输出描述:

对于每个询问输出相应的结果。

示例1
输入

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

输出

6
4
-3

说明

对于100%的数据，1<=n,m<=10^5，所有元素的范围和y的值在区间[-20000,20000]内。

dongtailianxuhe.cppview raw
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
/*
 区间查询，考虑用线段树
 两个子区间合并时，答案可能是来自三个部分
 （1）左区间
 （2）右区间
 （3）左区间右边的一段 和 右区间左边一段

 需要记录线段树区间左右两个端点向内延伸的最大和，用于合并


 */
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
struct node {
    int mx;//最大连续和
    int sum;//区间和
    int Lmx;//左端点向右的最大和
    int Rmx;//右端点向左的最大和
} tree[M<<2];
int A[M],n,m,a,b,f;
inline void Max(int &a,int b) {
    if(a<b)a=b;
}
inline void up(node &C,node A,node B) { //[A][B]合并成[C]
    C.sum=A.sum+B.sum;
    C.mx=max(A.mx,B.mx);
    Max(C.mx,A.Rmx+B.Lmx);
    C.Lmx=max(A.Lmx,A.sum+B.Lmx);
    C.Rmx=max(B.Rmx,B.sum+A.Rmx);
}
void build(int l,int r,int p) {
    if(l==r) {
        tree[p].mx=tree[p].Lmx=tree[p].Rmx=tree[p].sum=A[l];
        return;
    }
    int mid=l+r>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    up(tree[p],tree[p<<1],tree[p<<1|1]);
}
void update(int L,int R,int a,int x,int p) {
    if(L==R) {
        tree[p].mx=tree[p].Lmx=tree[p].Rmx=tree[p].sum=x;
        return;
    }
    int mid=L+R>>1;
    if(a<=mid)update(L,mid,a,x,p<<1);
    else update(mid+1,R,a,x,p<<1|1);
    up(tree[p],tree[p<<1],tree[p<<1|1]);
}
node query(int L,int R,int l,int r,int p) {
    if(L==l&&R==r)return tree[p];
    int mid=L+R>>1;
    if(r<=mid)return query(L,mid,l,r,p<<1);
    else if(l>mid)return query(mid+1,R,l,r,p<<1|1);
    else {
        node A=query(L,mid,l,mid,p<<1);
        node B=query(mid+1,R,mid+1,r,p<<1|1);
        node C;
        up(C,A,B);
        return C;
    }
}
int main() {
    cin>>n;
    for(int i=1; i<=n; ++i)
        scanf("%d",&A[i]);
    build(1,n,1);
    cin>>m;
    while(m--) {
        scanf("%d %d %d",&f,&a,&b);
        if(f) {
            node tmp=query(1,n,a,b,1);
            printf("%d\n",tmp.mx);
        } else update(1,n,a,b,1);
    }
    return 0;
}