kth

Kth

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

Poveste şi cerinţă...

Se da un vector V cu $N$ elemente. Asupra acestui vector aplicam $M$ operatii de $2$ tipuri:
 
* Operatia de tip $0$: se da un interval $[A, B]$ si un numar $K$. Sortam elementele din interval in ordine crescatoare dupa valoare, dupa care le inlocuim cu cea de a $K$-a valoare din acest interval.
* Operatia de tip $1$: se da un interval $[A, B]$ si un numar $K$. Toate elementele din acest interval sunt inlocuite cu valoarea $K$
 
Sa se afiseze vectorul de $N$ elemente la finalul celor $M$ operatii.

h2. Date de intrare

Fişierul de intrare $kth.in$ ...

Fişierul de intrare $kth.in$ va contine pe prima linie $2$ numere naturale $N$ si $M$. Pe a $2$-a linie vor fi $N$ numere naturale, reprezentand vectorul initial. Urmatoarele $M$ linii descriu update-urile. Un update consta din $4$ numere: $tip_update, A, B$ si $K$

h2. Date de ieşire

În fişierul de ieşire $kth.out$ ...

Fişierul de ieşire $kth.out$ va contine $N$ numere naturale aflate pe o singura linie, reprezentand vectorul V in urma celor $M$ update-uri.

h2. Restricţii

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

* $1 ≤ N, M ≤ 100.000$
* $1 ≤ K ≤ B - A + 1$ pentru operatiile de tip $0$
* Valorile initiale din vector, precum si valorile $K$ de la operatiile de tip $1$ vor fi cuprinse in intervalul $[1, 100.000]$
 

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

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

|5 3
1 3 2 3 4
0 2 4 2
0 4 5 2
1 3 4 10
|1 3 10 10 4

|

h3. Explicaţie
 
...

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