#P2670. Almost

    ID: 1727 传统题 4000ms 512MiB 尝试: 74 已通过: 26 难度: 9 上传者: 标签>CF2600省选/NOI-一维前缀和凸包叉积二分查找根号分块离线查询有理数精确运算欧几里得算法

Almost

题目描述

定义 nn 个数 X1,X2…Xn(n>1)X_1,X_2\dots X_n(n>1) 的几乎平均数为 ∑i=1nXi(n−1)\frac{\sum_{i=1}^{n} X_i}{(n-1)}。

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

输入格式

第一行包含两个正整数 NN 和 QQ。

第二行包含 NN 个整数,表示序列 SS。

接下来 QQ 行,每行包含两个整数 LL 和 RR,表示一个询问。

输出格式

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

若答案为整数 xx,输出 x1\frac{x}{1}。

输入样例

3 2
-2 -1 -2
1 2
1 3

输出样例

-3/1
-5/2

数据规模和约定

对于所有数据,∣Si∣≤106|S_i| \leq 10^6

数据点 NN QQ 数据点 NN QQ
11 1010 1111 3×1043 \times 10^4 10410^4
22 100100 1212 4×1044 \times 10^4
33 10001000 1313 5×1045 \times 10^4
44 20002000 1414 6×1046 \times 10^4 2×1042 \times 10^4
55 50005000 50005000 1515 7×1047 \times 10^4
66 10410^4 1616 8×1048 \times 10^4 3×1043 \times 10^4
77 10410^4 1717 9×1049 \times 10^4
88 2×1042 \times 10^4 50005000 1818 10510^5 1010
99 10410^4 1919 3×1043 \times 10^4