Question

Se consideră un șir a[1], a[2], …, a[n] de numere naturale. Se dau și T intervale închise de forma [x, y], cu x ≤ y.

Cerința
Pentru fiecare din cele T intervale de forma [x, y] trebuie să răspundeți la întrebarea: câte numere din șir aparțin intervalului [x, y]?

Date de intrare
Programul citește de la tastatură numerele n și T, apoi n numere naturale, separate prin spații, a[1], a[2], …, a[n]. Pe următoarele T linii se află câte două numere naturale x și y reprezentând un interval [x, y].

Date de ieșire
Programul va afișa pe ecran T linii. Pe fiecare linie i (i=1..T) se va afla un singur număr natural reprezentând răspunsul la a i-a întrebare.

Restricții și precizări
1 ≤ n, T ≤ 200 000
0 ≤ a[i] ≤ 2 000 000 000
0 ≤ x ≤ y ≤ 2 000 000 000
Exemplu
Intrare

9 7
6 1 3 5 3 3 9 20 9
4 10
0 100
0 1
500 506
3 3
10 18
3 9
Ieșire

4
9
1
0
3
0
7
Ajutati-ma va rog! Am fractiuni din codul pe care ar trebui sa l scriu, dar nu pot sa termin problema....

Answer 1

Solutia optima este cu cautare binara:
Complexitate O(T * log(n)


Ai sursa mai jos.

d0a2404fecef5f570661483de1a0362d.txt