Հերթագայված գումար
Ձեզ տրված է
n ամբողջ թվերից կազմված զանգված և q հարցում։ Հարցումները երկու տեսակ են. կամ պահանջում են թարմացնել զանգվածի որևէindeks p-ում գտնվող արժեքը, կամ հաշվել [l; r] ենթազանգվածի հերթագայված գումարը։Հերթագայված գումարը ենթազանգվածի
[l; r] համար սահմանվում է որպես տվյալ ենթազանգվածում զույգ կազմող ինդեքսների արժեքների գումարումից հանած կենտ կազմող ինդեքսների արժեքների գումարը։ Այլ կերպ ասած, եթե ենթազանգվածում [l; r] կան արժեքները, ապա հերթագայված գումարը առավել պատկերավոր արտահայտվում է այս կերպ. ։Յուրաքանչյուր հարցման (query) երկրորդ տեսակի համար պետք է հաշվել և տպել տրված ենթազանգվածի
[l; r] հերթագայված գումարը։Մուտք
Մուտքի առաջին տողում տրվում են երկու ամբողջ թվեր
n և q, որոնք համապատասխանաբար սահմանում են զանգվածի չափը և հարցումների քանակը (1 ≤ n, q ≤ ):Ելք
Յուրաքանչյուր հարցման (query) 2-րդ տիպի համար տպել հաշվարկված հերթագայված գումարը առանձին տողերում։
Օրինակներ
Мուտք | Ելք |
8 3
1 2 3 4 5 6 7 8
1 2 6
2 4 9
1 1 8 | 4
-9 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB