Laiko ribojimas: 1s
Atminties ribojimas: 256MB
Duomenų failas: segment_tree_2.in
Rezultatų failas: segment_tree_2.out
Masyvo užklausos 2
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ų:
- Elemento užklausa: rasti elemento
reikšmę
- 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 skaičius - elemento užklausos pozicija (
). 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šomo elemento reikšmę.
Pavyzdžiai
Pradiniai duomenys | Rezultatai |
---|---|
5 6 5 5 3 4 0 + 1 4 5 + 3 5 5 ? 3 + 1 2 0 + 3 5 1 ? 5 |
13 6 |
2 5 3 2 ? 1 ? 2 + 1 2 4 ? 1 ? 2 |
3 2 7 6 |