Almost

ID: 1727

传统题

4000ms

512MiB

尝试: 74

已通过: 26

难度: 5

上传者:

undefined

题目描述

定义 $n$ 个数 $X_1,X_2\dots X_n(n>1)$ 的几乎平均数为 $\frac{\sum_{i=1}^{n} X_i}{(n-1)}$ 。

对于给定的长度为 $N$ 的一个序列 $S$ ，需要回答 $Q$ 个询问。每个询问会给出 $L,R(1 \leq L < R \leq N)$ ，请找出 $a$ 与 $b(L \leq a < b \leq R)$ 使得 $S_a,S_{a+1},S_{a+2}\dots S_b$ 的几乎平均数最大。

输入格式

第一行包含两个正整数 $N$ 和 $Q$ 。

第二行包含 $N$ 个整数，表示序列 $S$ 。

接下来 $Q$ 行，每行包含两个整数 $L$ 和 $R$ ，表示一个询问。

输出格式

对于每个询问，输出一行，用一个既约分数表示最大的几乎平均数。

若答案为整数 $x$ ，输出 $\frac{x}{1}$ 。

输入样例

输出样例

-3/1
-5/2

数据规模和约定

对于所有数据， $|S_i| \leq 10^6$

数据点	$N$	$Q$	数据点	$N$	$Q$
$1$	$10$		$11$	$3 \times 10^4$	$10^4$
$2$	$100$		$12$	$4 \times 10^4$
$3$	$1000$		$13$	$5 \times 10^4$
$4$	$2000$		$14$	$6 \times 10^4$	$2 \times 10^4$
$5$	$5000$	$5000$	$15$	$7 \times 10^4$	$2 \times 10^4$
$6$	$10^4$	$5000$	$16$	$8 \times 10^4$	$3 \times 10^4$
$7$	$10^4$	$10^4$	$17$	$9 \times 10^4$	$3 \times 10^4$
$8$	$2 \times 10^4$	$5000$	$18$	$10^5$	$10$
$9$	$2 \times 10^4$	$10^4$	$19$	$10^5$	$3 \times 10^4$

#P2670. Almost

题目描述

输入格式

输出格式

输入样例

输出样例

数据规模和约定

状态

开发

支持

#P2670. Almost

Almost

题目描述

输入格式

输出格式

输入样例

输出样例

数据规模和约定

状态

开发

支持

登录