AcWing. 245你能回答这些问题吗(最大连续区间子段和)
给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
对于每个查询指令，输出一个整数表示答案。
输入格式
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改。
输出格式
对于每个查询指令输出一个整数表示答案。
每个答案占一行。
数据范围
N ≤ 500000 , M ≤ 100000
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 500010; int n, m; int a[N]; struct Node { int l, r; //区间左右端点 int tmax; //最大连续子段和 int lmax; //最大前缀 int rmax; //最大后缀 int sum; //区间和 }tr[N * 4]; void pushup(Node& u, Node& l, Node& r) { u.sum = l.sum + r.sum; u.lmax = max(l.lmax, l.sum + r.lmax); u.rmax = max(r.rmax, r.sum + l.rmax); u.tmax = max(l.tmax, r.tmax); u.tmax = max(u.tmax, l.rmax + r.lmax); } void pushup(int u) { pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); } void build(int u, int l, int r) { if (l == r)tr[u] = { l,r,a[r],a[r],a[r],a[r] }; else { tr[u] = { l,r }; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } int modify(int u, int x, int v) { if (tr[u].l == x && tr[u].r == x)tr[u] = { x,x,v,v,v,v }; else { int mid = tr[u].l + tr[u].r >> 1; if (x <= mid)modify(u << 1, x, v); else modify(u << 1 | 1, x, v); pushup(u); } } Node query(int u,int l,int r) { if (tr[u].l >= l && tr[u].r <= r)return tr[u]; else { int mid = tr[u].l + tr[u].r >> 1; if (r <= mid)return query(u << 1, l, r); else if (l > mid)return query(u << 1 | 1, l, r); else { auto left = query(u << 1, l, r); auto right = query(u << 1 | 1, l, r); Node res; pushup(res, left, right); return res; } } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n;++i)scanf("%d", &a[i]); build(1, 1, n); int k, x, y; while (m--) { scanf("%d%d%d", &k, &x, &y); if (k == 1) { if (x > y)swap(x, y); printf("%d\n", query(1, x, y).tmax); } else modify(1, x, y); } }
