macseq

Macseq

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

Gigel are un șir de *N* numere naturale, acesta vă cere ajutorul în rezolvarea a *Q* interogări de forma *L*, *R*, *X*. Pentru fiecare întrebare Gigel vrea să știe numarul de subsecvențe care sunt incluse in intervalul [*L*, *R*] și au maximul egal cu *X*.

Gigel are un șir de *N* numere naturale. Acesta vă cere ajutorul în rezolvarea a *Q* interogări de forma *L*, *R*, *X*. Pentru fiecare întrebare Gigel vrea să știe numarul de subsecvențe care sunt incluse in intervalul [*L*, *R*] și au maximul egal cu *X*.
 
O subsecvență este o submulțime de elemente ale șirului aflate pe poziții consecutive.

h2. Date de intrare

h2. Restricţii

h3. Subtaskul 1 (4 puncte)

* 1 ≤ *N*, *Q* ≤ 200.000
* 1 ≤ *L* ≤ *R* ≤ *N*
* 1 ≤ *X*, Numerele din șirul lui Gigel ≤ 10^9^
 
h3. Subtaskul 1 (6 puncte)
 
* 1 ≤ *N*, *Q* ≤ 300
 
h3. Subtaskul 2 (12 puncte)

h3. Subtaskul 2 (5 puncte)

* 1 ≤ *N* ≤ 5000
* Toate *X*-urile sunt sunt egale

h3. Subtaskul 3 (11 puncte)

h3. Subtaskul 3 (16 puncte)

h3. Substaskul 4 (20 puncte)

* 1 ≤ *N*, *Q* ≤ 2000
 
h3. Substaskul 4 (22 puncte)
 
* 1 ≤ *N*, *Q* ≤ 200.000
* Toate *X*-urile sunt sunt egale

h2. Exemplu

table(example). |_. macseq.in |_. macseq.out |

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

|6 3
15 33 55 33 12 46
1 6 33
2 4 33
1 6 55
|4
2
12

|
h3. Explicaţie

...

Subsecvențele care indeplinesc condițiile la prima interogare sunt [2,2], [1,2], [4,4], [4,5]. La a 2-a sunt [2,2] si [4,4].

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