कृपया मुझे रेंज मेक्स क्वेरी

Question

का कुशल एल्गोरिदम बताएं मुझे इस समस्या के बारे में कोई प्रश्न है।

प्रश्न

• आप एक दृश्य a[0], a 1],..., a[N-1] दिया जाता है, और सीमा (l[i], r[i]) (0 <= i <= Q - 1) की स्थापना की।
• सभी (l[i], r[i]) के लिए mex(a[l[i]], a[l[i] + 1],..., a[r[i] - 1]) की गणना करें।

फ़ंक्शन मैक्स न्यूनतम बहिष्कृत मान है।
Wikipedia Page of mex function

आप N <= 100000, Q <= 100000, and a[i] <= 100000 मान सकते हैं।
O(N * (r[i] - l[i]) log(r[i] - l[i])) एल्गोरिदम स्पष्ट है, लेकिन यह कुशल नहीं है।

मेरे वर्तमान दृष्टिकोण

#include <bits/stdc++.h> 
using namespace std; 
int N, Q, a[100009], l, r; 
int main() { 
    cin >> N >> Q; 
    for(int i = 0; i < N; i++) cin >> a[i]; 
    for(int i = 0; i < Q; i++) { 
     cin >> l >> r; 
     set<int> s; 
     for(int j = l; j < r; j++) s.insert(a[i]); 
     int ret = 0; 
     while(s.count(ret)) ret++; 
     cout << ret << endl; 
    } 
    return 0; 
} 

कृपया मुझे बताओ कैसे हल करने के लिए।

संपादित करें: ओ (एन^2) धीमा है। कृपया मुझे और तेजी से एल्गोरिदम बताओ।

Answer 1

यहाँ एक O((Q + N) log N) समाधान है:

1. बाएं से दाएं की सरणी में सभी पदों से अधिक पुनरावृति करते हैं और (एक खंड पेड़ में प्रत्येक मान के लिए पिछले घटनाओं की दुकान खंड पेड़ से प्रत्येक में कम से कम रखना चाहिए नोड)।

2. i -th संख्या जोड़ने के बाद, हम i के बराबर दाएं सीमा के साथ सभी प्रश्नों का उत्तर दे सकते हैं।

3. उत्तर सबसे छोटा मूल्य x है जो last[x] < l है। हम रूट से शुरू होने वाले सेगमेंट पेड़ को नीचे जाकर पा सकते हैं (यदि बाएं बच्चे में न्यूनतम l से छोटा है, तो हम वहां जाते हैं। अन्यथा, हम सही बच्चे के पास जाते हैं)।

यही है।

tree = new SegmentTree() // A minimum segment tree with -1 in each position 
for i = 0 .. n - 1 
    tree.put(a[i], i) 
    for all queries with r = i 
     ans for this query = tree.findFirstSmaller(l) 

छोटे समारोह लगता है इस प्रकार है::

यहाँ कुछ स्यूडोकोड है

int findFirstSmaller(node, value) 
    if node.isLeaf() 
     return node.position() 
    if node.leftChild.minimum < value 
     return findFirstSmaller(node.leftChild, value) 
    return findFirstSmaller(node.rightChild) 

यह समाधान नहीं बल्कि कोड के लिए आसान है (आप सभी की जरूरत के लिए एक बिंदु अद्यतन और findFisrtSmaller समारोह है ऊपर दिखाया गया है और मुझे यकीन है कि यह दिए गए बाधाओं के लिए पर्याप्त तेज़ है।

Answer 2

आइए प्रक्रिया दोनों हमारे प्रश्नों और एक बाएँ से सही ढंग से हमारे तत्वों, कुछ की तरह

for (int i = 0; i < N; ++i) { 
    // 1. Add a[i] to all internal data structures 
    // 2. Calculate answers for all queries q such that r[q] == i 
} 

यहाँ हम इस लूप के O(N) पुनरावृत्तियों है और हम डेटा संरचना के दोनों अद्यतन करना चाहते हैं और o(N) समय में वर्तमान में संसाधित भाग के प्रत्यय के उत्तर का उत्तर दें।

की सरणी contains[i][j] जो 1 प्रत्यय स्थिति i से शुरू करता है, तो है अन्यथा संख्या j और 0 शामिल उपयोग करते हैं। इस बात पर भी विचार करें कि हमने अलग-अलग contains[i] अलग-अलग के लिए उपसर्ग की गणना की है। इस मामले में हम बाइनरी खोज का उपयोग करते हुए O(log N) समय में प्रत्येक विशेष प्रत्यय क्वेरी का उत्तर दे सकते हैं: हमें केवल contains[l[i]] सरणी में पहला शून्य मिलना चाहिए जो वास्तव में पहली स्थिति है जहां आंशिक योग इंडेक्स के बराबर है, और सूचकांक + 1 नहीं दुर्भाग्यवश, ऐसे सरणी O(N^2) स्थान ले लेंगे और प्रत्येक अपडेट के लिए O(N^2) समय की आवश्यकता होगी।

तो, हमें अनुकूलित करना होगा। आइए "योग क्वेरी" और "असाइनमेंट" रेंज ऑपरेशंस के साथ 2-आयामी range tree बनाएं। इस पेड़ में हम किसी भी उप-आयत पर योग से पूछ सकते हैं और O(log^2 N) समय में किसी उप-आयत के सभी तत्वों को समान मान निर्दिष्ट कर सकते हैं, जो हमें O(log^2 N) समय और O(log^3 N) समय में प्रश्नों को अद्यतन करने की अनुमति देता है, समय जटिलता देता है O(Nlog^2 N + Qlog^3 N)। अंतरिक्ष जटिलता O((N + Q)log^2 N) (और सरणी के प्रारंभ के लिए एक ही समय) आलसी प्रारंभिकरण का उपयोग करके हासिल की जाती है।

यूपी: आइए संशोधित करें कि क्वेरी "योग" के साथ रेंज पेड़ों में कैसे काम करती है।1-आयामी पेड़ के लिए (इस जवाब बहुत लंबा नहीं बनाने के लिए), यह कुछ इस तरह है:

class Tree 
{ 
    int l, r;   // begin and end of the interval represented by this vertex 
    int sum;   // already calculated sum 
    int overriden;  // value of override or special constant 
    Tree *left, *right; // pointers to children 
} 
// returns sum of the part of this subtree that lies between from and to 
int Tree::get(int from, int to) 
{ 
    if (from > r || to < l) // no intersection 
    { 
     return 0; 
    } 
    if (l <= from && to <= r) // whole subtree lies within the interval 
    { 
     return sum; 
    } 
    if (overriden != NO_OVERRIDE) // should push override to children 
    { 
     left->overriden = right->overriden = overriden; 
     left->sum = right->sum = (r - l)/2 * overriden; 
     overriden = NO_OVERRIDE; 
    } 
    return left->get(from, to) + right->get(from, to); // split to 2 queries 
} 

यह देखते हुए कि हमारे विशेष मामले में पेड़ से सभी प्रश्नों उपसर्ग योग प्रश्न है, तो from हमेशा 0 के बराबर है, इसलिए, बच्चों को कॉल में से एक हमेशा एक छोटा जवाब देता है (0 या पहले से ही गणना sum)। तो, द्विआधारी खोज एल्गोरिदम में 2-आयामी पेड़ के लिए O(log N) क्वेरी करने के बजाय, हम खोज के लिए विज्ञापन-प्रक्रिया प्रक्रिया को कार्यान्वित कर सकते हैं, यह get क्वेरी के समान ही है। इसे पहले बाएं बच्चे का मूल्य प्राप्त करना चाहिए (जो O(1) लेता है क्योंकि इसकी पहले से गणना की जा चुकी है), फिर जांचें कि नोड जो हम खोज रहे हैं वह बाईं ओर है (यह योग बाएं उपट्री में पत्तियों की संख्या से कम है) और जाओ इस जानकारी के आधार पर बाईं ओर दाईं ओर। यह दृष्टिकोण O(log^2 N) समय (क्योंकि यह अब एक पेड़ ऑपरेशन है) के लिए क्वेरी को और अनुकूलित करेगा, जिससे O((N + Q)log^2 N)) दोनों समय और स्थान की परिणामी जटिलता दी जाएगी।

यह सुनिश्चित नहीं है कि यह समाधान Q और N दोनों 10^5 तक पर्याप्त तेज़ है, लेकिन शायद इसे और अनुकूलित किया जा सकता है।