अधिकतम उप-सरणी योग (Maximum Sum Subarray)
आपको
n पूर्णांकों (integers) की एक सरणी (array) और q प्रश्न (queries) दिए गए हैं। इन प्रश्नों के दो प्रकार होते हैं: किसी विशेष इंडेक्स p पर सरणी को अद्यतन (update) करना, तथा उप-सरणी [l; r] के भीतर अधिकतम उप-सरणी योग की गणना करना।उप-सरणी
[l; r] के भीतर अधिकतम उप-सरणी योग उस सतत (contiguous) उप-सरणी को कहते हैं जिसके तत्त्वों का योग सबसे अधिक हो। दूसरे शब्दों में, आपको [l'; r'] नामक उप-सरणी की खोज करनी होगी ताकि उसके तत्त्वों का योग [l; r] रेंज में आने वाली सभी गैर-खाली (non-empty) उप-सरणियों में अधिकतम हो।इनपुट (Input)
इनपुट की पहली पंक्ति में दो पूर्णांक
n और q होते हैं (1 ≤ n, q ≤ 100 000)।अगली पंक्ति में
n स्पेस से अलग किए गए पूर्णांक दिए होते हैं ( ≤ ≤ )।उसके बाद की
q पंक्तियों में सभी प्रश्न होते हैं, जिनका स्वरूप 1 l r (1 ≤ l ≤ r ≤ n) या 2 p x (1 ≤ p ≤ n, ≤ x ≤ ) हो सकता है। ये प्रश्न निम्न प्रकार के हैं:[l; r]उप-सरणी के भीतर अधिकतम उप-सरणी योग प्राप्त करें।
- सरणी के
pवें स्थान पर मानxसे अद्यतन (update) करें।
आउटपुट (Output)
प्रकार 1 वाले प्रत्येक प्रश्न के लिए, कार्यक्रम को उस प्रश्न का उत्तर प्रिंट करना चाहिए।
उदाहरण (Examples)
इनपुट | आउटपुट |
8 4
-2 1 -3 4 -7 2 1 -5
1 2 6
2 5 0
1 2 6
1 1 2 | 4
6
1 |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB