रेंज मिन-मैक्स क्वेरी
आपको
n तत्त्वों वाला एक ऐरे और q क्वेरी दी गई हैं। क्वेरी के दो प्रकार हैं:- दिए गए रेंज में न्यूनतम (minimum) और अधिकतम (maximum) प्राप्त करना
- ऐरे में किसी दिए गए स्थान पर अपडेट करना
आपका कार्य इन क्वेरी को कुशलतापूर्वक संसाधित करना है।
इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
n और q (1 ≤ n, q ≤ 100000) दिए जाते हैं, जो क्रमशः ऐरे में मौजूद तत्त्वों की संख्या और क्वेरी की संख्या का प्रतिनिधित्व करते हैं।दूसरी पंक्ति में
n स्पेस-सेपरेटेड पूर्णांक () होते हैं, जो ऐरे के शुरुआती तत्त्वों को दर्शाते हैं।इसके बाद की
q पंक्तियाँ प्रत्येक क्वेरी का वर्णन करती हैं:- रेंज मिनिमम और मैक्सिमम पेयर क्वेरी के लिए: पंक्ति की शुरुआत संख्या
1से होती है, जिसके बाद दो पूर्णांक और (1 ≤ li ≤ ri ≤ n) आते हैं। ये[l_i, r_i]रेंज का प्रतिनिधित्व करते हैं, जिसके लिए न्यूनतम और अधिकतम तत्त्वों का जोड़ा (pair) निकालना होता है।
- ऐरे को अपडेट करने की क्वेरी के लिए: पंक्ति की शुरुआत संख्या
2से होती है, जिसके बाद दो पूर्णांक और (1 ≤ pi ≤ n, 1 ≤ xi ≤ 10^9) आते हैं, जो उस तत्त्व के इंडेक्स और नए मान को दर्शाते हैं जिसे अपडेट किया जाना है।
आउटपुट
प्रत्येक रेंज मिनिमम और मैक्सिमम पेयर क्वेरी के लिए, दिए गए रेंज में मौजूद तत्त्वों का न्यूनतम और अधिकतम मूल्य, दो अलग-अलग पंक्तियों में प्रिंट करें।
उदाहरण
इनपुट | आउटपुट |
6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6 | 8 36
8 48
10 48 |
Constraints
Time limit: 0.9 seconds
Memory limit: 512 MB
Output limit: 1 MB