P10700 [SNCPC2024] 猜质数 II

为了悄悄准备一个神秘的质数，MCPlayer542 伤透了脑筋。 随后他发明了一种~~聪明~~愚蠢的办法，并起名为“质数分”。 他准备了 $n$ 个不同的数 $a_1,\ a_2,\ \ldots,\ a_n$ 作为测试点，并定义“质数分” $score(x,l,r)$ 如下： $$score(x,l,r)=\sum_{i=l}^r{f(x,a_i)}$$ 其中 $$f(x,y)=\left\{\begin{array}{rcl}u-y, & x=1 \\ u, & 1

输入数据的第一行包含两个整数 $n,\ q$ ($1\le n,\ q\le 5\times 10^5$)，用单个空格分隔。 第二行包含 $n$ 个整数 $a_1,\ a_2,\ \ldots,\ a_n$ ($1\le a_i\le 10^6$)，用单个空格分隔，表示测试点的数据。 接下来 $q$ 行，每行两个整数 $u_i,\ l_i$ ($1\le u_i \le 1.8\times 10^7,\ 1\le l_i\le n$)，用单个空格分隔，表示一次询问。

对每个询问输出一行两个数，即对应询问的最大得分和以及能获得该得分的最小 $r_i$ ($l_i\le r_i\le n$)，用单个空格分隔。

在样例 1 的第一个询问中，$u_1=14,\ l_1=4$。若我们选择 $r_1=6$，则最后的得分和为 $\sum_{i=1}^{10^6}{score(i,4,6)}$。其中： - $score(1,4,6)=13+9+11=33$； - $score(2,4,6)=0+14+14=28$； - $score(3,4,6)=0+14-9=5$； - $score(4,4,6)=0+14+0=14$； - $score(5,4,6)=0-25+0=-25$； - $i$ 取其他值时均有 $score(i,4,6)=0+0+0=0$。 故 $r_1=6$ 时得分和为 $33+28+5+14-25=55$。 可以证明在 $r_1$ 取其他值时无法得到更大的得分和，故答案为 $55$，且能达成的最小 $r_1$ 为 $6$。