传送门:>Here https://www.spoj.com/problems/GSS1/ <题意: 求区间最大子段和 $N \leq 50000$ 包括多组询问 (不需要支持修改)
解题思路
线段树的一道好题
考虑对于每一个节点, 维护四个信息: ls(代表当前区间一定顶着左端点的最大子段和),rs(同理, 一定顶着右端点的),sum(区间和),val(最大子段和, 也就是答案)
考虑进行转移 -- 一个节点的信息由它的两个子节点转移而来
$ls[rt] = Max(ls[rt*2], sum[rt*2] + ls[rt*2+1])$. 子段和之所以不包括整段区间是由于右端有负数. 因此再往右扩展不会更优
rs 同理转移. sum 就不说了
$val[rt] = Max\{ val[rt*1], val[rt*1+1], ls[rt], rs[rt], rs[rt*2]+ls[rt*2+1] \}$. 最难理解的是最后一部分.
想象一下, 当前区间的最大子段和要么有一头顶住端点, 要么两头都不碰到端点.
对于有一头一定碰到的情况, 直接用 $ls[rt] 和 rs[rt]$ 转移即可.(注意, 这里所说的是一定碰到, 当然最大子段也有可能碰到, 但是不一定)
对于都不碰到的情况, 如果其不跨过中间, 那么分别用两个子节点的 val 转移. 如果恰好跨过中间, 那我们需要把它拼接起来 -- 为了使答案最优, 我们考虑拼接 $rs[rt*2] 和 ls[rt*2+1]$ (仔细思考)
查询的时候也一样, 还是通过递归来完成转移. 这里需要对线段树的 query 有一个较为深刻的理解 -- 不同于 build,query(l,r) 表示的是区间 $[l, r]$ 中包含在查询区间的那一部分, 而不是真的 $[l, r]$. 因为在递归的时候我们会判断超界. 另外, 这里的转移需要刚才的四个参数, 因此 query 的返回值应当是一个结构体, 而不是单单一个数值. 我暂时还没有想出非结构体的做法......
- Code
- /*By DennyQi*/
- #include <cstdio>
- #include <queue>
- #include <cstring>
- #include <algorithm>
- #define r read()
- #define Max(a,b) (((a)>(b)) ? (a) : (b))
- #define Min(a,b) (((a)<(b)) ? (a) : (b))
- using namespace std;
- typedef long long ll;
- const int MAXN = 100010;
- const int MAXM = 27010;
- const int INF = 1061109567;
- inline int read(){
- int x = 0; int w = 1; register int c = getchar();
- while(c ^ '-' && (c <'0' || c> '9')) c = getchar();
- if(c == '-') w = -1, c = getchar();
- while(c>= '0' && c <= '9') x = (x <<3) + (x << 1) + c - '0', c = getchar(); return x * w;
- }
- int N,M,x,y,opt,a[MAXN];
- struct Data{ int ls,rs,sum,val; };
- struct SegmentTree{
- int ls[MAXN<<2], rs[MAXN<<2], sum[MAXN<<2], val[MAXN<<2];
- inline void Pushup(int rt){
- sum[rt] = sum[rt<<1] + sum[rt<<1|1];
- ls[rt] = Max(ls[rt<<1], sum[rt<<1]+ls[rt<<1|1]);
- rs[rt] = Max(rs[rt<<1|1], sum[rt<<1|1]+rs[rt<<1]);
- val[rt] = Max(Max(val[rt<<1], val[rt<<1|1]), Max(Max(ls[rt], rs[rt]), rs[rt<<1] + ls[rt<<1|1]));
- }
- void build(int L, int R, int rt){
- if(L>= R){
- val[rt] = sum[rt] = ls[rt] = rs[rt] = a[L];
- return;
- }
- int Mid = (L + R)>> 1;
- build(L, Mid, rt<<1);
- build(Mid+1, R, rt<<1|1);
- Pushup(rt);
- }
- Data query(int L, int R, int rt, int x, int y){
- if(x<=L && R<=y) return (Data){ls[rt],rs[rt],sum[rt],val[rt]};
- int Mid = (L + R)>> 1;
- if(y <= Mid) return query(L, Mid, rt<<1, x, y);
- if(x>= Mid+1) return query(Mid+1, R, rt<<1|1, x, y);
- Data res, t_1 = query(L, Mid, rt<<1, x, y), t_2 = query(Mid+1, R, rt<<1|1, x, y);
- res.sum = t_1.sum + t_2.sum;
- res.ls = Max(t_1.ls, t_1.sum + t_2.ls);
- res.rs = Max(t_2.rs, t_1.rs + t_2.sum);
- res.val = Max(Max(t_1.val, t_2.val), Max(Max(res.ls, res.rs), t_1.rs + t_2.ls));
- return res;
- }
- }qxz;
- int main(){
- N=r;
- for(int i = 1; i <= N; ++i) a[i] = r;
- qxz.build(1, N, 1);
- M=r;
- for(int i = 1; i <= M; ++i){
- x = r, y = r;
- printf("%d\n", qxz.query(1, N, 1, x, y).val);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2717647.html