K-th Set Bit (के-थ सेट बिट)
आपके पास एक बाइनरी ऐरे (binary array) है जिसका आकार
n है, जिसमें 0 और 1 शामिल हैं। ऐरे के तत्व 1 से n तक क्रमांकित हैं। आपको q क्वेरीज़ को प्रोसेस करना है, जिनमें से प्रत्येक क्वेरी दो प्रकारों में से एक हो सकती है:- क्वेरी प्रकार 1: ऐरे में 1 की
k-वीं बार आने वाली पोज़िशन (इंडेक्स) खोजें।
- क्वेरी प्रकार 2: ऐरे के किसी खास इंडेक्स पर मौजूद मान को अपडेट करें।
आपको एक ऐसा प्रोग्राम लिखना होगा जो इन क्वेरीज़ को कुशलता से हल कर सके।
Input (इनपुट)
इनपुट की पहली पंक्ति में दो पूर्णांक
n और q होंगे, जिनके बीच में एक स्पेस होगा। n बाइनरी ऐरे का आकार दर्शाता है और q क्वेरीज़ की संख्या।दूसरी पंक्ति में ऐरे के
n बाइनरी एलिमेंट्स दिए जाते हैं।इसके बाद की
q पंक्तियाँ क्वेरीज़ का विवरण देती हैं। प्रत्येक क्वेरी को एक क्वेरी प्रकार (1 या 2) के साथ लिखा जाता है, जिसके बाद आवश्यक पैरामीटर आते हैं:- क्वेरी प्रकार 1 के लिए: एक पूर्णांक
k(1 ≤ k ≤ n)।
- क्वेरी प्रकार 2 के लिए: एक पूर्णांक इंडेक्स
p(1 ≤ p ≤ n) और अपडेट किए जाने वाला मान ( या )।
Output (आउटपुट)
प्रत्येक क्वेरी प्रकार 1 के लिए, ऐरे में 1 की
k-वीं आवृत्ति का इंडेक्स प्रिंट करें। अगर k-वीं आवृत्ति मौजूद न हो, तो -1 प्रिंट करें।Examples (उदाहरण)
Input | Output |
6 4
1 0 1 1 0 1
1 2
2 1 0
1 4
1 3 | 3
-1
6 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB