首页 > 试题广场 >

小美的数组询问

[编程题]小美的数组询问
  • 热度指数:659 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小美拿到了一个由正整数组成的数组,但其中有一些元素是未知的(用 0 来表示)。
现在小美想知道,如果那些未知的元素在区间[l,r]范围内随机取值的话,数组所有元素之和的最小值和最大值分别是多少?
共有q次询问。

输入描述:
第一行输入两个正整数n,q,代表数组大小和询问次数。
第二行输入n个整数a_i,其中如果输入的a_i为 0,那么说明a_i是未知的。
接下来的q行,每行输入两个正整数 l,r,代表一次询问。
1\leq n,q \leq 10^5
0 \leq a_i \leq 10^9
1\leq l \leq r \leq 10^9


输出描述:
输出q行,每行输出两个正整数,代表所有元素之和的最小值和最大值。
示例1

输入

3 2
1 0 3
1 2
4 4

输出

5 6
8 8

说明

只有第二个元素是未知的。
第一次询问,数组最小的和是 1+1+3=5,最大的和是 1+2+3=6。
第二次询问,显然数组的元素和必然为 8。