TR-M4. Bo‘lim jamg‘armasi

Litsey tuzilmasi — n ta bo‘limli daraxt, ildizi 1. i-bo‘lim hisobida aᵢ so‘m bor. q ta amal:

• 1 v x — v bo‘lim hisobi x ga teng bo‘ldi;
• 2 v — v bo‘lim va uning barcha quyi bo‘limlari hisoblari yig‘indisi qancha?

Kirish ma’lumotlari

Birinchi qatorda n, ikkinchisida a₁ … aₙ, keyin n − 1 ta qirra u v. Keyin q, so‘ng q ta amal.

Chiqish ma’lumotlari

Har 2-turdagi amalga alohida qatorda javob.

Cheklovlar

1 ≤ n, q ≤ 2·10⁵; 0 ≤ aᵢ, x ≤ 10⁹.

1-misol: 3-bo‘lim shoxida 3, 4, 5 — 3 + 4 + 5 = 12; 4-bo‘lim 10 bo‘lgach — 18.