子段和 正解

Part -1 题目描述

here

Part 0 一些闲话

你：哇这个……三个\(\sum\)耶！！！\(\mathcal{O}(n^3)\)算法？不不不，\(n\leq10^5\)！！！但我只会\(\mathcal{O}(n^2)\)的前缀和优化！！！怎么办，怎么办……

然后你就点到了这里，~~一个 404 Page~~。

Part 1 题目剖析

算法 #1

时间复杂度：\(\mathcal{O}(n^3)\)

空间复杂度：\(\mathcal{O}(n)\)

期望得分：\(10\)pts

暴力枚举进行求和即可。

算法 #2

时间复杂度：\(\mathcal{O}(n^2)\)

空间复杂度：\(\mathcal{O}(n)\)

期望得分：\(30\)pts

观察此题公式。它的含义是：

给定一个序列\(a\)，求它所有子序列中数的和之和。

~~好别扭啊！！！~~

于是我们直接前缀和优化，并暴力枚举左右两端点即可\(\mathcal{O}(n^2)\)求得答案。

算法 #3（正解 1）

时间复杂度：\(\mathcal{O}(3n)\)

空间复杂度：\(\mathcal{O}(2n)\)

期望得分：\(100\)pts

（至于时空间复杂度为什么加系数……为了更便于比较与算法 #4 的优劣）

先说结论吧。

为在算法 #2 的基础上得到的前缀和数组（命名为\(b\)）进行一次后缀和操作，得到数组\(c\)。于是

\[\sum_{i=1}^{i\leq n}c_i-b_{i-1}\times(n-i+1)\]

即为答案。

证明在这里。

此算法想出需要：

1. 一张纸（~~废话~~）
2. 更多纸（~~搞笑~~）
3. 聪慧的脑子
4. 没了

算法 #4（正解 2）

时间复杂度：\(\mathcal{O}(n)\)

空间复杂度：\(\mathcal{O}(1)\)

期望得分：\(100\)pts

（以上复杂度是真的没系数）

此算法想出需要：

1. 普通的脑子
2. 没了

同样先给出结论，答案为：

\[\sum_{i=1}^{i\leq n}a_i\times i\times(n-i+1)\]

很简单，画图啊！！！（以\(3\)号为例）

|   |   |
+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+
|   |   | <- 左端点

            |   |   |   |
+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+
  右端点 -> |   |   |   |

每两个左右端点都可以组成一个包含\(3\)号的一段，即\(3\)号一共出现了\(3\times4=12\)（次）。设它是\(13\)，则它对答案的贡献应该是\(13\times12=156\)，\(\mathcal{O}(n)\)即可求得。

你还想要代码？嗯哼哼……