Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | arbquery.in, arbquery.out | Sursă | Science On 2021, clasele 11-12 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Sandulescu Alexandru •alexsandulescu |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 268435 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arbquery
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
Primul rând al fişierului de intrare arbquery.out conţine numărele N şi Q. Urmează N - 1 rânduri, fiecare conţinând trei valori x, y, l, ce indică existenţa unei muchii de la x la y cu lungimea l. Urmează apoi Q linii, fiecare conţinând două valori x, y, ce reprezintă o interogare asupra lanţului unic de la x la y.
Date de ieşire
Fişierul de ieşire arbquery.out conţine răspunsurile celor Q interogări, în ordine.
Subtaskuri
- Subtask 1 (10 puncte)
- N, Q ≤ 20.
- Oricare muchie are lungimea cel mult 105.
- Subtask 2 (30 puncte)
- N, Q ≤ 2.000.
- Oricare muchie are lungimea cel mult 105.
- Subtask 3 (10 puncte)
- N, Q ≤ 100.000.
- Oricare nod are cel mult 2 muchii incidente.
- Oricare muchie are lungimea cel mult 105.
- Subtask 4 (10 puncte)
- N, Q ≤ 100.000.
- Cel mult un nod are mai mult de 1 muchie incidentă.
- Oricare muchie are lungimea cel mult 105.
- Subtask 5 (40 puncte)
- N, Q ≤ 100.000.
- Oricare muchie are lungimea cel mult 105.
Exemplu
| hiperquery.in | hiperquery.out |
|---|---|
| 3 3 1 2 1 2 3 100 1 2 2 3 1 3 | 102 201 303 |
Observăm că sunt trei lanţuri, 1 - 2 de cost 1, 2 - 3 de cost 100 şi 1 - 2 - 3 de cost 101. Astfel d(1, 2) = 102, d(2, 3) = 201. Astfel rezultatul pentru 1, 2 este d(1, 2) = 102, pentru 2, 3 este d(2, 3) = 201, şi pentru 1, 3 este d(1, 2) + d(2, 3) = 303.
