RainAir
My OI Blog
RainAir
Can you answer these queries III

题目描述

题目链接

给定一个长度为 $n$ 的序列 $a$,有 $q$ 个询问,询问有两种:

  • 单点修改

  • 给定一组 $L,R$,求

    $$max{\Sigma_{i=l}^{r}a_i}(L\leq l \leq r \leq R)$$

其中 $n,q \leq 50000$。

解题报告

这个有和,我们可以用线段树维护。

线段树需要维护四个值:当前区间的前缀最大值,当前区间的后缀最大值,当前区间的答案,以及区间和。

这些显然可以通过线段树合并来实现。

前缀最大值 = max(左儿子的前缀最大值,左儿子的和 + 右儿子的前缀最大值)

后缀最大值 = max(右儿子的后缀最大值,右儿子的和 + 左儿子的后缀最大值)

答案 = max(左儿子的答案,右儿子的答案,左儿子的后缀最大值 + 右儿子的前缀最大值)

也就是考虑相交和不相交的部分然后合并了。

具体见代码。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/55
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

Can you answer these queries III
题目描述 题目链接 给定一个长度为 $n$ 的序列 $a$,有 $q$ 个询问,询问有两种: 单点修改 给定一组 $L,R$,求 $$max{\Sigma_{i=l}^{r}a_i}(L\leq l \leq r \leq R)$$ …
扫描二维码继续阅读
2018-10-02
标签
近期评论