तो मैं इस प्रोग्रामिंग समस्या को हल करने की कोशिश कर रहा था।सुबारै प्रश्न
संख्याओं और कुछ प्रश्नों की एक श्रृंखला को देखते हुए। प्रत्येक क्वेरी आपको तीन नंबर ए, बी, सी देता है और आपको इंडेक्स से सभी तत्वों के सूचकांक बी (दोनों शामिल) के उत्तर देने के लिए कहता है जो सी से कम या उसके बराबर हैं।
उदाहरण के लिए:
को देखते हुए सरणी: {} 2,4,6,1,5,1,6,4,5,4
3 प्रश्नों का जवाब दिया जा करने के लिए कर रहे हैं:
2 से 4 4 -> ans = 5 यानी {4 + 1}
1 5 3 -> ans = 3 यानी {2 + 1}
4 5 1 -> ans = 1
प्रत्येक सरणी में मान 10^5 से कम है, सरणी की लंबाई और प्रश्नों की संख्या 10^5
यहां मैंने क्या किया है मैंने प्रश्नों को हल करने के लिए मो के एल्गोरिदम (स्क्वायर रूट अपघटन) का उपयोग किया है, और बनाया है 1-10^5 से सभी मानों से कम तत्वों के संचयी योग को संग्रहीत करने के लिए एक बाइनरी अनुक्रमित पेड़, और प्रश्नों से प्रश्नों के लिए एक अद्यतन को अद्यतन किया। इस एल्गोरिदम के साथ मेरे समाधान की समग्र जटिलता ओ (क्यू * वर्ग (एन) * लॉग (एन) है लेकिन यह पर्याप्त तेज़ नहीं है। मैं एक बेहतर एल्गोरिदम की तलाश में था। मुझे लगता है कि प्रश्नों का वर्ग-रूट अपघटन काम नहीं करेगा। क्या इस समस्या को हल करने के लिए कोई बेहतर एल्गोरिदम है?
मैं सोच रहा था कि क्या कुछ डेटा-संरचना इस समस्या को हल कर सकती है जिसे मैं अनजान हूं?
आपका मतलब है "ए", "बी", "सी" इंडेक्स हैं? और क्या आप शून्य-आधारित अनुक्रमण का उपयोग कर रहे हैं? – Bahrom
@ बाह्रोम ए और बी '1' आधारित सूचकांक हैं, सी एक संख्या है। – ash