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*.
 
O subsecvență este o submulțime de elemente ale șirului aflate pe poziții consecutive.

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

h2. Date de intrare

h2. Restricţii

* 1 ≤ *N*, *Q* ≤ 200.000
* 1 ≤ *L* ≤ *R* ≤ *N*
* 1 ≤ *X*, Numerele din șirul lui Gigel ≤ 10^9^

* 1 ≤ *N* ≤ 200.000
* 1 ≤ *Q* ≤ 300.069
* Numerele din șirul lui Gigel ≤ 10^9^
* 1 ≤ *L*, *R* ≤ *N*
* 1 ≤ *X* ≤ 10^9^

h3. Subtaskul 1 (6 puncte)

h3. Subtaskul 1 (4 puncte)

* 1 ≤ *N*, *Q* ≤ 300

h3. Subtaskul 2 (12 puncte)

h3. Subtaskul 2 (5 puncte)

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

* 1 ≤ *N* ≤ 2000
* Toți *X* sunt egali

h3. Subtaskul 3 (16 puncte)

h3. Subtaskul 3 (11 puncte)

* 1 ≤ *N*, *Q* ≤ 2000

h3. Substaskul 4 (22 puncte)

h3. Substaskul 4 (12 puncte)
 
* 1 ≤ *N*, *Q* ≤ 10.000
* Toți *X* sunt egali
 
h3. Substaskul 5 (12 puncte)

* 1 ≤ *N*, *Q* ≤ 200.000

* Toate *X*-urile sunt sunt egale

Toți *X* sunt egali

h2. Exemplu

h3. Subtaskul 6 (20 puncte)
 
* 1 ≤ *N*, *Q* ≤ 10.000
h2. Exemplu

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

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

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

|
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") ==