Acwing 245.你能回答这些问题吗

标签：

题目描述

给定长度为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; }

Acwing 245.你能回答这些问题吗

标签：

原文地址：https://www.cnblogs.com/yangxuejian/p/11565453.html