Laiko ribojimas: 1s
Atminties ribojimas: 256MB
Duomenų failas: segment_tree_5.in
Rezultatų failas: segment_tree_5.out
Masyvo Uzklausos
Jūs turite masyvą, sudarytą iš sveikųjų skaičių
,
,
, ...,
. Jūsų uždavinys - įvykdyti
užklausų turimai skaičių sekai.
Užklausos gali būti dviejų tipų:
- Sumos užklausa: apskaičiuoti elementų
sumą.
- Pridėjimo užklausa: prie sekos elementų
pridėti skaičių
.
Pradiniai duomenys
Pirmoje eilutėje pateikti du skaičiai ir
(
), atitinkamai nurodantys masyvo elementų skaičių bei užklausų kiekį.
Antroje eilutėje pateikta skaičių
: pradinės elementų reikšmės.
.
Kitose eilučių pateikti užklausų duomenys: Simbolis
- užklausos tipas (
?
arba +
). Jei yra
?
, tai toje eilutėje taip pat yra du skaičiai ir
- sumuojamo intervalo pradžia ir pabaiga (
). Jei
yra
+
, tai toje eilutėje toliau yra trys skaičiai: - pridėjimo užklausos intervalo pradžia, pabaiga, ir prie elementų pridedama reikšmė (
).
Rezultatai
Kiekvienai ?
tipo užklausai išveskite prašomų elementų sumą.
Pavyzdžiai
Pradiniai duomenys | Rezultatai |
---|---|
5 6 5 5 3 4 0 + 1 4 5 + 3 5 5 ? 2 4 + 1 2 0 + 3 5 1 ? 3 5 |
37 35 |
2 7 3 2 ? 1 1 ? 2 2 ? 1 2 + 1 2 4 ? 1 1 ? 2 2 ? 1 2 |
3 2 5 7 6 13 |