suma6

Suma6

== include(page="template/taskheader" task_id="suma6") ==

Se dau două numere naturale $N$ şi $S$ şi un şir de $N$ numere naturale $a$ ~1~, $a$ ~2~ ... $a$ ~N~.

Se dau două numere naturale $N$ şi $S$ şi un şir de $N$ numere naturale $a${~1~}, $a${~2~} ... $a${~N~}.

h2. Cerinţă

Să se răspundă la $Q$ query-uri de tipul $(L,R)$, pentru fiecare query precizând numărul de perechi $(i,j)$, $L ≤ i < j ≤ R$ cu proprietatea $a$ ~i~ + $a$ ~j~ = $S$.

Să se răspundă la $Q$ query-uri de tipul $(L,R)$, pentru fiecare query precizând numărul de perechi $(i,j)$, $L ≤ i < j ≤ R$ cu proprietatea $a{~i~} + a{~j~} = S$.

h2. Date de intrare

Fişierul de intrare $suma6.in$ conţine pe prima linie numerele naturale $N$ şi $S$. Pe a 2-a linie se află valorile $a$ ~1~, $a$ ~2~ ... $a$ ~N~ separate prin exact un spaţiu. Linia a 3-a conţine $Q$, numărul de query-uri iar pe fiecare dintre următoarele $Q$ linii, se află două numere $L R$ separate printr-un spaţiu, corespunzătoare unui query.

Fişierul de intrare $suma6.in$ conţine pe prima linie numerele naturale $N$ şi $S$. Pe a 2-a linie se află valorile $a{~1~}, a{~2~} ... a{~N~}$ separate prin exact un spaţiu. Linia a $3$-a conţine $Q$, numărul de query-uri iar pe fiecare dintre următoarele $Q$ linii, se află două numere $L R$ separate printr-un spaţiu, corespunzătoare unui query.

h2. Date de ieşire

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 100.000$
* $1 ≤ Q ≤ 200.000$

* $0 ≤ a ~i~ ≤ 1.000.000, 1 ≤ i ≤ N$

* $0 ≤ a{~i~} ≤ 1.000.000, 1 ≤ i ≤ N$

* $1 ≤ L ≤ R ≤ N$
* $0 ≤ S ≤ 1.000.000$

h3. Explicaţie

De exemplu, pentru ultimul query $1 6$, cele $3$ perechi sunt: $a ~1~ + a ~4~ = 10; a ~2~ + a ~5~ = 10; a ~4~ + a ~6~ = 10.$

De exemplu, pentru ultimul query $1 6$, cele $3$ perechi sunt: $a{~1~} + a{~4~} = 10; a{~2~} + a{~5~} = 10; a{~4~} + a{~6~} = 10$.

== include(page="template/taskfooter" task_id="suma6") ==