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 V[L], V[L+1], ..., V® sunt egale cu X. Pot exista query-uri în care L > R caz în care vrem numărul de numere din <tex> V_L, ... , V_N, V_1, ... , V_R <\tex> 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 10⁵.

• Subtask 2 (30 puncte)
  • N, Q ≤ 2.000.
  • Oricare muchie are lungimea cel mult 10⁵.

• Subtask 3 (10 puncte)
  • N, Q ≤ 100.000.
  • Oricare nod are cel mult 2 muchii incidente.
  • Oricare muchie are lungimea cel mult 10⁵.

• 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 10⁵.

• Subtask 5 (40 puncte)
  • N, Q ≤ 100.000.
  • Oricare muchie are lungimea cel mult 10⁵.

Exemplu

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.

Cum se trimit solutii?