题解 SP1043 【GSS1 - Can you answer these queries I】
Paranoid丶离殇
2019-09-26 17:01:31
题目传送门：[SP1043 GSS1 - Can you answer these queries I](https://www.luogu.org/problem/SP1043)
[更好的阅读体验](https://www.cnblogs.com/Paranoid-LS/p/11592810.html)
### 静态维护子段和最大值
提供结构体指针线段树写法：
设$l$为区间左端点， $r$为区间右端点；
$ls$为以$l$为左端点的最大子段和, $rs$为以$r$为右端点的最大子段和;
$sum$为区间和, $val$为区间子段和最大和。
$ch[0]$为左儿子, $ch[1]$为右儿子.
考虑维护：
> o->sum = ch[0]->sum + ch[1]->sum;
>
> o->ls = max(ch[0]->ls, ch[0]->sum + ch[1]->ls);
>
> o->rs = max(ch[1]->rs, ch[1]->sum + ch[0]->rs);
>
> o->val = max(max(ch[0]->val, ch[1]->val), max(max(o->ls, o->rs), ch[0]->rs + ch[1]->ls);
这样可以考虑到所有的转移情况；
在询问时, 若询问区间跨过左右两个子区间, 则我们利用$ls, rs, sum$来更新出当前区间的$val$;
所以我们返回结构体指针。
### code：
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 5e4 + 5;
int read() {
int x = 0, f = 1; char ch;
while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(x = ch^48; isdigit(ch = getchar()); x = (x<<3) + (x<<1) + (ch^48));
return x * f;
}
int n, m;
template <class T> T Max(T a, T b) { return a > b ? a : b; }
struct Segment {
struct node {
int l, r, ls, rs, sum, val;
node *ch[2];
node(int l, int r, int ls, int rs, int sum, int val) : l(l), r(r), ls(ls), rs(rs), sum(sum), val(val) {
ch[0] = ch[1] = NULL;
}
inline int mid() { return (l + r) >> 1; }
inline void up() {
sum = ch[0]->sum + ch[1]->sum;
ls = Max(ch[0]->ls, ch[0]->sum + ch[1]->ls);
rs = Max(ch[1]->rs, ch[1]->sum + ch[0]->rs);
val = Max(Max(ch[0]->val, ch[1]->val), Max(Max(ls, rs), ch[0]->rs + ch[1]->ls));
}
} *root;
void build(node *&o, int l, int r) {
o = new node(l, r, 0, 0, 0, 0);
if(l == r) {
o->ls = o->rs = o->sum = o->val = read();
return;
}
build(o->ch[0], l, o->mid());
build(o->ch[1], o->mid() + 1, r);
o->up();
}
node *query(node *o, int l, int r) {
if(l <= o->l && o->r <= r) return o;
if(r <= o->mid()) return query(o->ch[0], l, r);
if(l > o->mid()) return query(o->ch[1], l, r);
node *res = new node(l, r, 0, 0, 0, 0);
node *t1 = query(o->ch[0], l, r), *t2 = query(o->ch[1], l, r);
res->sum = t1->sum + t2->sum;
res->ls = Max(t1->ls, t1->sum + t2->ls);
res->rs = Max(t2->rs, t2->sum + t1->rs);
res->val = Max(Max(t1->val, t2->val), Max(Max(res->ls, res->rs), t1->rs + t2->ls));
return res;
}
} tr;
int main() {
n = read();
tr.build(tr.root, 1, n);
m = read();
for(int i = 1, l, r; i <= m; ++ i) {
l = read(); r = read();
printf("%d\n", tr.query(tr.root, l, r)->val);
}
return 0;
}
```