Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:1024 MB

#79. 二分查找3

附加文件 统计

有 $n$ 个数 $a_1, a_2, \dots, a_n$ 和 $m$ 个询问。

每次询问给两个数 $l, r$,回答这些数字里面有多少个数字大于等于 $l$ 并且小于等于 $r$,并且求出这些数字的和。

输入格式

第一行两个整数 $n, m$。接下来一行 $n$ 个整数,表示 $a_1, a_2, \dots, a_n$。

接下来 $m$ 行,每行两个整数 $l, r$。

输出格式

输出 $m$ 行,每行两个整数,表示数字个数和他们的和。

样例输入1

5 5
5 1 3 1 5
2 5
1 3
1 2
1 4
1 3

样例输出1

3 13
3 5
2 2
3 5
3 5

样例输入2

20 20
270655754 207478908 184247637 347980009 856846407 863201545 298689973 330306148 737540196 181644174 985151980 109340906 971996692 27296089 133462958 523531634 637454529 223596029 723122460 546959966
214062377 913946329
372303496 931697657
180354787 966075376
519785253 898450527
99834558 285194729
613181269 858929057
292533683 933357306
392352947 909697513
196993467 526071921
33927592 961651350
136565764 628097493
420683356 752017460
325407254 415827967
267582486 348704395
358889809 669564145
70089407 473236116
261089899 782078008
196595430 306454184
902207923 945385162
693649817 992663767

样例输出2

12 6359884650
7 4888656737
15 6933255369
7 4888656737
7 1310426366
4 2954963592
10 5865632867
7 4888656737
7 2202238455
17 7176059233
10 3115090232
5 3168608785
2 678286157
4 1247631884
3 1707946129
10 2287402496
9 4416240669
4 1000420664
0 0
6 5137859280

数据规模

对于 $100\%$ 的数据,满足 $1\leq n,m\leq 10^5, 1\leq a_i\leq 10^9, 1\leq l\leq r\leq 10^9$。