https://www.acwing.com/problem/content/246/
一个很有意思的线段树,一般来说要求的最大连续和只需要维护一个从左侧开始/从右侧开始的最大连续和用来跨越区间中点,但是这里居然至少要包含一个元素,所以要进行一些变形。主要是叶子节点里面的各个标记至少要有一个元素。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 500000;
//MAXLSUM和MAXRSUM表示一直从左侧/右侧点开始的最大和,MAXSUM表示无限制的最大和,SUM表示和
ll MAXLSUM[(1 << 20) + 5], MAXRSUM[(1 << 20) + 5], SUM[(1 << 20) + 5], MAXSUM[(1 << 20) + 5];
int A[MAXN + 5];
inline void PushUp(const int &o) {
MAXLSUM[o] = max(MAXLSUM[o << 1], SUM[o << 1] + max(MAXLSUM[o << 1 | 1], 0ll));
MAXRSUM[o] = max(MAXRSUM[o << 1 | 1], SUM[o << 1 | 1] + max(MAXRSUM[o << 1], 0ll));
MAXSUM[o] = max(max(MAXSUM[o << 1], MAXSUM[o << 1 | 1]), max(max(MAXRSUM[o << 1], 0ll) + MAXLSUM[o << 1 | 1], MAXRSUM[o << 1] + max(MAXLSUM[o << 1 | 1], 0ll)));
SUM[o] = SUM[o << 1] + SUM[o << 1 | 1];
}
inline void Build(const int &o, const int &l, const int &r) {
if(l == r) {
MAXLSUM[o] = MAXRSUM[o] = MAXSUM[o] = SUM[o] = A[l];
return;
}
int mid = l + r >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
PushUp(o);
}
inline void Update(const int &o, const int &l, const int &r, const int &x, const int &y) {
if(l == r) {
MAXLSUM[o] = MAXRSUM[o] = MAXSUM[o] = SUM[o] = A[l] = y;
return;
}
int mid = l + r >> 1;
if(x <= mid)
Update(o << 1, l, mid, x, y);
else
Update(o << 1 | 1, mid + 1, r, x, y);
PushUp(o);
}
const ll INF = 1e18;
inline ll QueryMAXLSUM(const int &o, const int &l, const int &r, const int &ql, const int &qr) {
if(ql <= l && r <= qr) {
return MAXLSUM[o];
}
int mid = l + r >> 1;
ll res = -INF;
if(ql <= mid)
res = QueryMAXLSUM(o << 1, l, mid, ql, qr);
if(qr >= mid + 1)
res = max(res, SUM[o << 1] + max(QueryMAXLSUM(o << 1 | 1, mid + 1, r, ql, qr), 0ll));
return res;
}
inline ll QueryMAXRSUM(const int &o, const int &l, const int &r, const int &ql, const int &qr) {
if(ql <= l && r <= qr) {
return MAXRSUM[o];
}
int mid = l + r >> 1;
ll res = -INF;
if(qr >= mid + 1)
res = QueryMAXRSUM(o << 1 | 1, mid + 1, r, ql, qr);
if(ql <= mid)
res = max(res, SUM[o << 1 | 1] + max(QueryMAXRSUM(o << 1, l, mid, ql, qr), 0ll));
return res;
}
inline ll QueryMAXSUM(const int &o, const int &l, const int &r, const int &ql, const int &qr) {
if(ql <= l && r <= qr) {
return MAXSUM[o];
}
int mid = l + r >> 1;
ll res = -INF;
if(ql <= mid)
res = QueryMAXSUM(o << 1, l, mid, ql, qr);
if(qr >= mid + 1)
res = max(res, QueryMAXSUM(o << 1 | 1, mid + 1, r, ql, qr));
if(ql <= mid && qr >= mid + 1) {
ll tmpL = QueryMAXRSUM(o << 1, l, mid, ql, qr);
ll tmpR = QueryMAXLSUM(o << 1 | 1, mid + 1, r, ql, qr);
res = max(res, max(tmpL + max(tmpR, 0ll), max(tmpL, 0ll) + tmpR));
}
return res;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d", &A[i]);
}
Build(1, 1, n);
while(m--) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if(op == 1) {
if(x > y)
swap(x, y);
printf("%lld\n", QueryMAXSUM(1, 1, n, x, y));
} else {
Update(1, 1, n, x, y);
}
}
}
实际上已经保证至少有一个元素之后一部分max可以去掉。
inline void PushUp(const int &o) {
MAXLSUM[o] = max(MAXLSUM[o << 1], SUM[o << 1] + max(MAXLSUM[o << 1 | 1], 0ll));
MAXRSUM[o] = max(MAXRSUM[o << 1 | 1], SUM[o << 1 | 1] + max(MAXRSUM[o << 1], 0ll));
MAXSUM[o] = max(max(MAXSUM[o << 1], MAXSUM[o << 1 | 1]), max(max(MAXRSUM[o << 1], 0ll) + MAXLSUM[o << 1 | 1], MAXRSUM[o << 1] + max(MAXLSUM[o << 1 | 1], 0ll)));
SUM[o] = SUM[o << 1] + SUM[o << 1 | 1];
}
因为MAXLSUM[o]>=SUM[o],且MAXRSUM[o]>=SUM[o],所以可以去掉前两个max操作使得常数变小。
而第三个max操作,假如有某个前缀/后缀和是负数的话,那么最大值肯定是落在其中一个区间的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 500000;
//MAXLSUM和MAXRSUM表示一直从左侧/右侧点开始的最大和,MAXSUM表示无限制的最大和,SUM表示和
ll MAXLSUM[(1 << 20) + 5], MAXRSUM[(1 << 20) + 5], SUM[(1 << 20) + 5], MAXSUM[(1 << 20) + 5];
int A[MAXN + 5];
inline void PushUp(const int &o) {
MAXLSUM[o] = max(MAXLSUM[o << 1], SUM[o << 1] + MAXLSUM[o << 1 | 1]);
MAXRSUM[o] = max(MAXRSUM[o << 1 | 1], SUM[o << 1 | 1] + MAXRSUM[o << 1]);
MAXSUM[o] = max(max(MAXSUM[o << 1], MAXSUM[o << 1 | 1]), max(MAXRSUM[o << 1] + MAXLSUM[o << 1 | 1], MAXRSUM[o << 1] + MAXLSUM[o << 1 | 1]));
SUM[o] = SUM[o << 1] + SUM[o << 1 | 1];
}
inline void Build(const int &o, const int &l, const int &r) {
if(l == r) {
MAXLSUM[o] = MAXRSUM[o] = MAXSUM[o] = SUM[o] = A[l];
return;
}
int mid = l + r >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
PushUp(o);
}
inline void Update(const int &o, const int &l, const int &r, const int &x, const int &y) {
if(l == r) {
MAXLSUM[o] = MAXRSUM[o] = MAXSUM[o] = SUM[o] = A[l] = y;
return;
}
int mid = l + r >> 1;
if(x <= mid)
Update(o << 1, l, mid, x, y);
else
Update(o << 1 | 1, mid + 1, r, x, y);
PushUp(o);
}
const ll INF = 1e18;
inline ll QueryMAXLSUM(const int &o, const int &l, const int &r, const int &ql, const int &qr) {
if(ql <= l && r <= qr) {
return MAXLSUM[o];
}
int mid = l + r >> 1;
ll res = -INF;
if(ql <= mid)
res = QueryMAXLSUM(o << 1, l, mid, ql, qr);
if(qr >= mid + 1)
res = max(res, SUM[o << 1] + QueryMAXLSUM(o << 1 | 1, mid + 1, r, ql, qr));
return res;
}
inline ll QueryMAXRSUM(const int &o, const int &l, const int &r, const int &ql, const int &qr) {
if(ql <= l && r <= qr) {
return MAXRSUM[o];
}
int mid = l + r >> 1;
ll res = -INF;
if(qr >= mid + 1)
res = QueryMAXRSUM(o << 1 | 1, mid + 1, r, ql, qr);
if(ql <= mid)
res = max(res, SUM[o << 1 | 1] + QueryMAXRSUM(o << 1, l, mid, ql, qr));
return res;
}
inline ll QueryMAXSUM(const int &o, const int &l, const int &r, const int &ql, const int &qr) {
if(ql <= l && r <= qr) {
return MAXSUM[o];
}
int mid = l + r >> 1;
ll res = -INF;
if(ql <= mid)
res = QueryMAXSUM(o << 1, l, mid, ql, qr);
if(qr >= mid + 1)
res = max(res, QueryMAXSUM(o << 1 | 1, mid + 1, r, ql, qr));
if(ql <= mid && qr >= mid + 1) {
ll tmpL = QueryMAXRSUM(o << 1, l, mid, ql, qr);
ll tmpR = QueryMAXLSUM(o << 1 | 1, mid + 1, r, ql, qr);
res = max(res, tmpL + tmpR);
}
return res;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d", &A[i]);
}
Build(1, 1, n);
while(m--) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if(op == 1) {
if(x > y)
swap(x, y);
printf("%lld\n", QueryMAXSUM(1, 1, n, x, y));
} else {
Update(1, 1, n, x, y);
}
}
}