Alternating Sum
आपके पास n पूर्णांकों की एक array और q क्वेरीज़ हैं। इन क्वेरीज़ के दो प्रकार हैं: किसी दिए गए इंडेक्स p पर array को अपडेट करना, तथा उपarray [l; r] का alternating sum निकालना।
उपarray [l; r] का alternating sum इस तरह परिभाषित है कि इसमें सब-एरे के सम में समांक (even) इंडेक्स के तत्वों को जोड़कर, विषम (odd) इंडेक्स के तत्वों को घटाया जाता है। दूसरे शब्दों में, यदि उपarray [l; r] में तत्व [al, a{l+1}, ..., a_r] हैं, तो इसका alternating sum
al - a{l+1} + a{l+2} - a{l+3} + ... + (-1)^{r-l} · a_r
इनपुट
पहली पंक्ति में दो पूर्णांक n और q दिए जाते हैं, जो क्रमशः array का आकार और क्वेरीज़ की संख्या दर्शाते हैं (1 ≤ n, q ≤ 10^5)।
आउटपुट
प्रकार 2 की प्रत्येक क्वेरी के लिए, प्राप्त alternating sum को एक पृथक पंक्ति में प्रदर्शित करें।
उदाहरण
Input | Output |
|---|---|
8 3 | 4 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB