题目描述
给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 maxx≤l≤r≤y{∑ri=lA[i]}。
2、“2 x y”，把 A[x] 改成 y。
对于每个查询指令，输出一个整数表示答案。
输入格式
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改。
输出格式
对于每个查询指令输出一个整数表示答案。
每个答案占一行。
数据范围
N≤500000,M≤100000
输入样例：
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2
输出样例：
2
-1
时/空限制：
1s / 64MB
rt。
一道挺难的线段树题。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 5;
struct seg{
int ans, sum, l, r, L, R;
#define ans(p) t[p].ans
#define sum(p) t[p].sum
#define l(p) t[p].l
#define r(p) t[p].r
#define L(p) t[p].L
#define R(p) t[p].R
}t[maxn << 2];
int num[maxn];
void build(int p, int l, int r){
l(p) = l; r(p) = r;
if(l == r){
sum(p) = ans(p) = L(p) = R(p) = num[l];
return ;
}
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1 , mid + 1, r);
sum(p) = sum(p << 1) + sum(p << 1 | 1);
L(p) = max(L(p << 1), sum(p << 1) + L(p << 1 | 1));
R(p) = max(R(p << 1 | 1), sum(p << 1 | 1) + R(p << 1));
int sondata = max(ans(p << 1), ans(p << 1 | 1));
ans(p) = max(sondata, L(p << 1 | 1) + R(p << 1));
}
void change(int p, int d, int k){
if(d < l(p) || d > r(p))
return ;
if(l(p) == r(p)){
sum(p) = ans(p) = L(p) = R(p) = k;
return ;
}
change(p << 1, d, k);
change(p << 1 | 1, d, k);
sum(p) = sum (p << 1) + sum (p << 1 | 1);
L(p) = max(L(p << 1), sum(p << 1) + L(p << 1 | 1));
R(p) = max(R(p << 1 | 1), sum(p << 1 | 1) + R(p << 1));
int sondata = max(ans(p << 1), ans(p << 1 | 1));
ans(p) = max(sondata, L(p << 1 | 1) + R(p << 1));
}
seg query(int p ,int l, int r){
if(l <= l(p) && r(p) <= r){
return t[p];
}
seg lson, rson, res;
int mid = l(p) + r(p) >> 1, val = -1e9;
lson = (seg){val, val, 0, 0, val, val};
rson = lson;
res.sum = 0;
if(l <= mid){
lson = query(p << 1, l, r);
res.sum += lson.sum;
}
if(mid < r){
rson = query(p << 1 | 1, l, r);
res.sum += rson.sum;
}
int answer = max(lson.ans, rson.ans);
res.ans = max(answer, lson.R + rson.L);
res.L = max(lson.L, lson.sum + rson.L);
res.R = max(rson.R, rson.sum + lson.R);
if(l > mid)
res.L = max(res.L, rson.L);
if(r <= mid)
res.R = max(res.R, lson.R);
return res;
}
signed main(){
int n, m;
scanf("%lld%lld", &n, &m);
for(int i = 1;i <= n;i ++)
scanf("%lld", &num[i]);
build(1, 1, n);
//printf ("[TESTDATA] the root rlen answer is %d. \n", R(3));
for(int i = 1;i <= m;i ++){
int x, y, z;
scanf("%lld%lld%lld", &x, &y, &z);
if(x == 1){
if(y > z)
swap(y, z);
printf("%lld\n", query(1, y, z).ans);
} else {
change(1, y, z);
}
}
return 0;
}