| Fişierul intrare/ieşire: | hiperquery.in, hiperquery.out | Sursă | Science On 2021, clasele 11-12 |
| Autor | Mihai-Cristian Popescu, Tamio-Vesa Nakajima | Adăugată de |  Apostol Daniel •ApostolIlieDaniel |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 268435 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Hiperquery
Se dă un şir circular de numere naturale V de lungime N, indexat de la 1. Numerele din şir se află în intervalul închis [1, N], iar prima şi ultima poziţie sunt considerate adiacente.
Sunt definite următoarele operaţii:
- Update X, Y: elementul de pe poziţia X devine Y
- Rotate X: roteşte spre dreapta şirul cu X poziţii (şirul [1, 2, 3, 4] rotit cu o poziţie spre dreapta devine [4, 1, 2, 3])
- Query L R X: câte numere din şir, din subsecvenţa
sunt egale cu X. Pot exista query-uri în care L > R caz în care vrem numărul de numere din 
care sunt egale cu X
Dându-se şirul iniţial se cere să se proceseze un şir de operaţii dat.
Date de intrare
Pe prima linie a fişierului de intrare hiperquery.in se găseşte numărul N.
Pe următoarea linie se află N numere naturale care formează şirul V.
Pe următoarea linie se află un număr M urmat de M linii pe care sunt descrise operaţiile date:
- Pentru update: 1 X Y
- Pentru rotire: 2 X
- Pentru query: 3 L R X
Date de ieşire
În fişierul de ieşire hiperquery.out se vor găsi răspunsurile la întrebări, fiecare pe câte un rând.
Subtaskuri
- Subtask 1 (10 puncte)
- 1 ≤ N ≤ 1.000.
- 1 ≤ M ≤ 1.000.
- Subtask 2 (30 puncte)
- 1 ≤ N ≤ 100.000.
- 1 ≤ M ≤ 100.000.
- Nu există operaţii de tipul 1.
- Subtask 3 (30 puncte)
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 100.000
- Nu există operaţii de tipul 2.
- Subtask 4 (30 puncte)
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 100.000
Exemplu
| hiperquery.in | hiperquery.out |
|---|---|
| 4 4 1 3 1 6 3 2 4 1 3 3 1 4 3 3 2 1 1 1 2 2 2 3 1 1 3 | 2 1 2 1 |
Pentru prima întrebare subsecvenţa este: [4, 1, 3, 1]
Pentru a doua întrebare subsecvenţa este [4, 1, 3, 1]
Pentru a treia întrebare subsecvenţa este întreg şirul.
După primul update şirul devine: [2,1,3,1]
Dupa rotire şirul devine: [3,1,2,1]
Pentru ultima întrebare subsecvenţa este: [3,1,2,1]
