Project Euler 663
Project Euler 663
题目
Sums of subarrays
Let
For a given integer
The array is changed iteratively by replacing
After each step
The first 6 steps for
Initial state:
Step
Step
Step
Step
Step
Step
Let
You are given
Find
线段树
线段树是一种用于维护区间内的数的一些计算结果,这些计算需要满足结合律(如加法,乘法,最小值,最大值)。假设这个序列为
- 树的每个节点都代表一个区间的统计结果。
- 根节点代表着整个区间
,每个叶节点代表着某一个长度为 的区间 。 - 如果当前节点代表的区间为
,那么左子节点代表的区间是 ,右子节点是 ,其中 。
线段树的三个操作:
- 建树(初始化)。给定一个序列,自底向上地建立出一颗线段树。当两个子节点的信息维护好时,当前节点的信息也能迅速维护好。单次操作仅需要
的时间复杂度。建树一旦完成,以后就不需要进行操作了。 - 修改。从根节点往下搜索,递归找到需要修改的整个区间。修改完成后,再自底向上更新所有祖先节点的信息。单次操作仅需要
的时间复杂度。 - 查询。从根节点往下搜索,如果查询的区间覆盖了当前整个区间,那么直接返回当前节点的信息;如果查询的区间和左 / 右子节点有交集,那么递归查询后,将结果合并。最终向上传递。单次操作也仅需要
的时间复杂度。
因此,维护好各个节点,可以以高效的方式维护出需要结果的值。
解决方案
考虑使用线段树解决本题。每个节点
|
|
|
|
|
那么,假设
这说明当前区间的答案要么是取自左子节点,要么是取自右子节点;要么是左子节点的最大后缀进和与右子节点的最大前缀和合并形成一个新的答案。 | |
这说明当前区间的最大前缀和要么是来自左子节点的最大前缀和,要么是左子节点的整个区间和右子节点的最大前缀和合并形成当前区间的前缀。 | |
与最大前缀和类似。 | |
其它仅需要遵循线段树的模式即可。
代码
第一份代码,严格在线段树上执行了计算
第二份代码,则减少了一部分没有必要的工作。由于计算的
1 | # include <bits/stdc++.h> |
1 | # include <bits/stdc++.h> |