RainAir
My OI Blog
RainAir
GSS 系列题目题解

记录一下本人目前会做的 GSS 系列题目。

目前已经完成 GSS1,GSS3,GSS4,GSS5。

GSS1

题目描述

求最大子段和,序列的值可能为负数。

其中长度 $\leq 50000$。

解题报告

线段树维护这个序列。

线段树中维护四个值:$sum,lans,rans,ans$,分别表示当前序列的和,前缀最大值,后缀最大值,和最大子段和。

合并的时候暴力维护一下就可以了。

时间复杂度 $O(nlog_2n)$。

代码

GSS3

个人博客链接

一点都没变……中间直接加上单点修改的操作就行了。

可以去我之前写的博客里观看,写的比较详细。

GSS4

题目描述

维护一个序列,支持下列操作:

  1. 区间开方(向下取整)
  2. 区间和

其中区间长度 $\leq 10^5$,所有元素的和 $\leq 10^{18}$。

解题报告

发现数一直开方最后会变成 $0$ 或 $1$ 。我们直接维护区间最大值就可以,当最大值 $\leq 1$ 的时候就不需要修改,否则暴力递归下去即可。因为数不是很大,$10^9$ 范围的数开方 $9$ 次就不用开方了,复杂度得以保证。

代码

GSS5

题目描述

$GSS1$的升级版。这次限定左端点在 $[x_1,y_1]$ 之间,右端点在 $[x_2,y_2]$ 之间。

解题报告

只需要分类讨论一下就可以了qwq

如果 $y_1 \leq x_2$ 即两段区间没有交点,那么一定是 $[x_1,y_1]$ 的后缀最大值加上 $[y_1,x_2]$ 的和(必须经过)加上 $[x_2,y_2]$ 的前缀最大值。

https://blog.aor.sd.cn/wp-content/uploads/2018/11/QQ20181011-193402.png

如果有交点 ($y_1 > x_2$),那么就要进行一波分类讨论:

https://blog.aor.sd.cn/wp-content/uploads/2018/11/QQ20181011-193752.png

第一条线段:当 $x_2 \leq x,y \leq y_1$ 的时候,只需要求出 $[x_2,y_1]$ 的最大子段和。

第二条线段:当 $x_1 \leq x < x_2,x_2 \leq y \leq y_1$ 的时候,答案是 $[x_1,x_2)$ 的最大后缀和 $+$ $[x_2,y_1] $ 的最大前缀和。

第三条线段:当 $x_2 \leq x \leq y_1,y_1 < y \leq y_2$ 的时候,答案是$[x_2,y_1]$ 的最大后缀和 $+$ $(y_1,y_2]$ 的最大前缀和。

第四条线段:当 $x_1 \leq x < x_2,y_1 < y \leq y_2$ 的时候,答案是 $[x_1,x_2)$ 的最大后缀和 $+$ $[x_2,y_1]$ 的区间和 $+$ $(y_1,y_2]$ 的最大前缀和。

注意特判一下不是必选的区间和 $0$ 比较就可以了,还有一定要在查询的时候判断区间不可行退出,还要注意区间临界点处理的细节。

还有不要定义 $y1,y2$ 这种变量,会和 $cmath$ 库冲突的。

总体来说还是很水的,代码细节比较多

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/52
如文中无特殊声明,本文采用 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

GSS 系列题目题解
记录一下本人目前会做的 GSS 系列题目。 目前已经完成 GSS1,GSS3,GSS4,GSS5。 GSS1 题目描述 求最大子段和,序列的值可能为负数。 其中长度 $\leq 50000$。 解题报告 线段树维护…
扫描二维码继续阅读
2018-10-11
标签
近期评论