P11235 [KTSC 2024 R1] 最大化平均值

**请勿用 C++14 (GCC 9) 提交本题** 你需要在程序开头加入如下代码： ```cpp #include #include void initialize(std::vector A); std::array maximum_average(int i, int j); ``` 题目保证时限在标程的十倍以上，交互库代码运行很快。

**题目译自 [2024년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2024/) T1 「[평균 최대화](https://assets.ioikorea.kr/ioitst/2024/1/average/average_statement.pdf)」** 给定一个由正整数组成的长度为 $m$ $(m \geq 2)$ 的序列 $x[0], \cdots, x[m-1]$，如果该序列满足以下条件，则称其为**封闭序列**： - 对于所有 $k$ $(1 \leq k \leq m-2)$，$x[k] > x[0]$ 且 $x[k] > x[m-1]$。 也就是说，如果序列 $x$ 的两端元素都小于中间的所有元素，那么 $x$ 就是一个封闭序列。例如，$[3,7,8,4,2]$ 和 $[7,7]$ 是封闭序列，但 $[5,8,4,6,7]$ 和 $[3,3,4]$ 不是封闭序列。注意，长度为 $2$ 的所有序列都是封闭序列，而长度小于等于 $1$ 的序列不是封闭序列。 给定一个长度为 $K$ 的序列 $X[0], \cdots, X[K-1]$，定义**剔除操作**为选择一个封闭序列 $X[i], \cdots, X[j]$，并从序列中移除 $X[i+1], \cdots, X[j-1]$（即将序列变为 $X[0], \cdots, X[i], X[j], \cdots, X[K-1]$）。定义 $f(X)$ 为通过任意次数的剔除操作（可以不使用，也可以多次使用）得到的最终序列的最大平均值。 例如，$f([1,3,2,100,97,98,2,3,4,1])=43$，可以通过以下剔除操作实现： - 选择 $i=0, j=2$，将序列变为 $[1,2,100,97,98,2,3,4,1]$。 - 选择 $i=5, j=8$，将序列变为 $[1,2,100,97,98,2,1]$。 - 最终序列为 $[1,2,100,97,98,2,1]$，其平均值为 $(1+2+100+97+98+2+1) / 7=43$。 给定一个由正整数组成的长度为 $N$ 的序列 $A[0], \cdots, A[N-1]$。对于每个给定的封闭序列 $(i, j)$，你需要计算 $f(A[i], \cdots, A[j])$ 的值。 你需要实现以下函数： ```cpp void initialize(std::vector A); ``` - 该函数只会被调用一次，并且在其他所有函数调用之前调用。 - `A`：大小为 $N$ 的整数数组。 - 如果需要进行预处理或设置全局变量，可以在此函数中实现。 ```cpp std::array maximum_average(int i, int j); ``` - $0 \leq i < j \leq N-1$，且 $A[i], \cdots, A[j]$ 是一个封闭序列。 - 该函数应返回 $f(A[i], \cdots, A[j])=s / t$，其中 $[s, t]$ 是一个数组。 - $s$ 和 $t$ 是 $1$ 到 $10^{18}$ 之间的整数。可以证明，对于所有满足约束条件的输入，答案总能表示为这种形式的分数。 - 该函数会被调用 $Q$ 次。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N$ - 第 $2$ 行：$A[0]\,A[1]\,\cdots \,A[N-1]$ - 第 $3$ 行：$Q$ - 第 $3+k$ $(1 \leq k \leq Q)$ 行：$i[k]\,j[k]$（第 $k$ 次调用 `maximum_average` 函数的参数）

示例评测程序输出： - 第 $k$ 行：第 $k$ 次调用 `maximum_average` 返回的数组中的两个整数

对于所有输入数据，满足： - $2 \leq N \leq 3\cdot 10^5$ - $1 \leq Q \leq 6\cdot 10^5$ - 对于所有 $i$ $(0 \leq i \leq N-1)$，$1 \leq A[i] \leq 10^7$ - 对于所有 `maximum_average` 调用，$0 \leq i < j \leq N-1$，且 $A[i], \cdots, A[j]$ 是一个封闭序列。 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $5$ | $N \leq 15$ | | $2$ | $6$ | $N \leq 50$ | | $3$ | $13$ | $N \leq 250$ | | $4$ | $7$ | 对于所有 $i$ $(0 \leq i \leq N-1)$，$A[i] \leq 4$ | | $5$ | $12$ | $N \leq 5000$ | | $6$ | $17$ | $A$ 是一个封闭序列；$Q=1$，且调用 `maximum_average(0, N-1)`，即只需计算整个序列 $A$ 的答案 | | $7$ | $8$ | 对于所有 $i$ $(0 \leq i \leq N-1)$，$A[i] \leq 20$ | | $8$ | $32$ | 无附加限制 |