Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: segment_tree_4.in

Rezultatų failas: segment_tree_4.out

Jei norite pateikti savo sprendimą - prisijunkite.

Masyvo užklausos 4

O tai įdomesnių uždavinių negalėjai padaryti? - Gediminas, probably.

Jūs turite masyvą, sudarytą iš n sveikųjų skaičių a_1, a_2, a_3, ..., a_n. Jūsų uždavinys - įvykdyti q užklausų turimai skaičių sekai.

Užklausos gali būti dviejų tipų:

  1. Sumos užklausa: apskaičiuoti elementų a_l,a_{l+1},...a_r sumą.
  2. Įrašymo užklausa: sekos elementų a_l,a_{l+1},...a_r reikšmes pakeisti į reikšmę d.

Pradiniai duomenys

Pirmoje eilutėje pateikti du skaičiai n ir q (1\\leqn,q\\leq200000), atitinkamai nurodantys masyvo elementų skaičių bei užklausų kiekį.

Antroje eilutėje pateikta n skaičių a_i: pradinės elementų reikšmės. 1\\leqa_1,a_2,a_3,...,a_n\\leq200000.

Kitose q eilučių pateikti užklausų duomenys: Simbolis c - užklausos tipas (? arba !). Jei c yra ?, tai toje eilutėje taip pat yra du skaičiai l ir r - sumuojamo intervalo pradžia ir pabaiga (1\\leql\\leqr\\leqn). Jei c yra !, tai toje eilutėje toliau yra trys skaičiai: l,r,d - įrašymo užklausos intervalo pradžia, pabaiga, ir nauja elementų reikšmė (1\\leql\\leqr\\leqn,1\\leqd\\leq200000).

Rezultatai

Kiekvienai ? tipo užklausai išveskite prašomų elementų sumą.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 6
5 5 3 4 1
! 1 4 5
! 3 5 5
? 2 4
! 1 2 3
! 3 5 1
? 2 5
 
15
6
 
2 7
3 2
? 1 1
? 2 2
? 1 2
! 1 2 4
? 1 1
? 2 2
? 1 2
 
3
2
5
4
4
8