文档章节

[SP1043] GSS1 - Can you answer these queries I

o
 osc_4nmshwhm
发布于 2018/08/07 10:28
字数 978
阅读 3
收藏 0

精选30+云产品,助力企业轻松上云!>>>

传送门:>Here<

题意:求区间最大子段和 $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;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

在C#中,公共,私有,受保护和没有访问修饰符之间有什么区别?

问题: All my college years I have been using public , and would like to know the difference between public , private , and protected ? 在我上大学的所有学年中,我一直都在使用pub......

法国红酒甜
13分钟前
5
0
unity的UGUI之中锚点(Anchors)和中心点(Pivot)、Shift和Alt键功能

在UGUI的控件属性之中,最上方的Rect Transform一栏可以看到锚点和中心点: 锚点Anchors 控件用于定位自身的基准点 可以点击左上角的方框,在其中选择锚点的不同方式: 注意图中,黄色的小点...

路过暴风
今天
7
0
如何将div放置在其容器的底部? - How can I position my div at the bottom of its container?

问题: Given the following HTML: 鉴于以下HTML: <div id="container"> <!-- Other elements here --> <div id="copyright"> Copyright Foo web designs </div> </div> I would like #cop......

富含淀粉
今天
10
0
学习编写编译器[关闭] - Learning to write a compiler [closed]

问题: Preferred languages : C/C++, Java, and Ruby. 首选语言 :C / C ++,Java和Ruby。 I am looking for some helpful books/tutorials on how to write your own compiler simply for......

技术盛宴
今天
17
0
OSChina 周一乱弹 —— 毛巾又怎么样?!我在乎的是大姐姐温柔的怀抱!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《雨 因你而下,于你而止》- Seto 手机党少年们想听歌,请使劲儿戳(这里) @Dan...

小小编辑
今天
54
2

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部