给定长度为N的数组A,以及M条指令,每条指令可能是以下两种之一:
- 1 x y,查询区间[x,y]中的最大连续子段和。
- 2 x y,把A[x]改成y。
对于每个询问,输出一个整数表示答案。
数据限制:N<=5e5, M<=1e5, |A[i]|<=1000。
提示:线段树,每个区间需要维护答案、前缀、后缀以及区间和。
#include <bits/stdc++.h>
template<class Info>
struct SegmentTree {
int n;
std::vector<Info> info;
SegmentTree():n(0) {}
SegmentTree(int _n, Info v = Info()) {
init(_n, v);
}
void init(int _n, Info v = Info()) {
init(std::vector<Info>(_n, v));
}
template<class T>
SegmentTree(std::vector<T> v) {
init(v);
}
template<class T>
void init(std::vector<T> v) {
n = v.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int,int,int)> build = [&](int x, int l, int r) {
if (l + 1 == r) {
info[x] = v[l]; //fixme
return;
}
int m = (l + r) / 2;
build(2*x+1, l, m);
build(2*x+2, m, r);
pushup(x);
};
build(0, 0, n);
}
void pushup(int x) {
info[x] = info[2*x+1] + info[2*x+2];
}
void modify(int x, int l, int r, int p, const Info &v) {
if (l + 1 == r) {
info[x] = v; //fixme
return;
}
int m = (l + r) / 2;
if (p < m) {
modify(2*x+1, l, m, p, v);
} else {
modify(2*x+2, m, r, p, v);
}
pushup(x);
}
void modify(int p, const Info &v) {
modify(0, 0, n, p, v);
}
Info rangeQuery(int x, int l, int r, int L, int R) {
if (R <= l || r <= L) {
return Info();
}
if (L <= l && r <= R) {
return info[x];
}
int m = (l + r) / 2;
return rangeQuery(2*x+1, l, m, L, R) + rangeQuery(2*x+2, m, r, L, R);
}
Info rangeQuery(int L, int R) {
return rangeQuery(0, 0, n, L, R);
}
template<class F>
int findFirst(int x, int l, int r, int L, int R, F pred) {
if (R <= l || r <= L || !pred(info[x])) {
return -1;
}
if (l + 1 == r) {
return l;
}
int m = (l + r) / 2;
int res = findFirst(2*x+1, l, m, L, R, pred);
if (res == -1) {
res = findFirst(2*x+2, m, r, L, R, pred);
}
return res;
}
template<class F>
int findFirst(int L, int R, F pred) {
return findFirst(0, 0, n, L, R, pred);
}
template<class F>
int findLast(int x, int l, int r, int L, int R, F pred) {
if (R <= l || r <= L || !pred(info[x])) {
return -1;
}
if (l + 1 == r) {
return l;
}
int m = (l + r) / 2;
int res = findLast(2*x+2, m, r, L, R, pred);
if (res == -1) {
res = findLast(2*x+1, l, m, L, R, pred);
}
return res;
}
template<class F>
int findLast(int L, int R, F pred) {
return findLast(0, 0, n, L, R, pred);
}
};
struct Info {
int val, pre, suf, sum;
static const int inf = 1e8;
Info(int v=inf):val(v),pre(v),suf(v),sum(v) {}
friend Info operator+(const Info &a, const Info &b) {
if (a.val == inf) {
return b;
}
if (b.val == inf) {
return a;
}
Info ans;
ans.val = std::max(a.suf + b.pre, std::max(a.val, b.val));
ans.pre = std::max(a.pre, a.sum+b.pre);
ans.suf = std::max(a.suf+b.sum, b.suf);
ans.sum = a.sum + b.sum;
return ans;
}
};
void solve() {
int N, M;
std::cin >> N >> M;
std::vector<int> A(N);
for (int i = 0; i < N; i++) {
std::cin >> A[i];
}
SegmentTree<Info> seg(A);
for (int i = 0; i < M; i++) {
int k, x, y;
std::cin >> k >> x >> y;
if (k == 1) {
x--, y--;
if (x > y) {
std::swap(x, y);
}
std::cout << seg.rangeQuery(x, y+1).val << "\n";
} else {
x--;
seg.modify(x, Info(y));
}
}
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t = 1;
while (t--) solve();
return 0;
}
标签:Info,CH4301,return,val,子段,int,sum,std,区间
From: https://www.cnblogs.com/chenfy27/p/18259555