seuOJ203 - 小 Q 的数列

小 Q 在帮他的同学 JSZKC 验题。

题目大意如下：有一个长度为 $n$ 的数列，数列共有 $n-m+1$ 个长度为 $m$ 的连续子序列，要求出所有连续子序列的最大值的和。

小 Q 觉得这道题太水了，他决定出一道更难的题目：

以如下规则生成一个长度为 $n$ 的伪随机数列： $A_1 = 6563116 , A_{i+1} = A_i \times A_i\ mod\ 32745673$ 。

可见， ${A_i}$ 的最初五项是 $6563116, 14723431, 19804172, 20943262, 21546875$ 。

定义 $M(i, j)$ 是 $A_i, A_{i+1}, A_{i+2}, \ldots, A_j$ 这 $j-i+1$ 个数的中位数。

F(n, m) = \sum_{i=1}^{n-m+1} M(i, i + m - 1)

小 Q 希望你对于输入的 $n$ 和 $m$ 求出 $F(n, m)$ 。

第一行两个整数 $n(2 \leq n \leq 10^6)$ 和 $m(2\leq m \leq min\{10^5,\ n\}，2|m)$ ，表示数列长度和连续子序列的长度。

共一行，输出一个数 $F(n, m)$ 。

5 2

69525860.5