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$
* $1 ≤ L ≤ R ≤ N$
* $0 ≤ S ≤ 1.000.000$

h2. Exemplu
table(example). |_. suma6.in |_. suma6.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 10 10
1 4 8 9 6 1 10 4 12 1
5
1 4
1 10
5 6
4 6
1 6
| 1
5
0
1
3

|
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$.

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