CSES रेंज क्वेरी प्रश्न: वेतन क्वेरी

Question

मैं इस समस्या को हल करने की कोशिश कर रहा हूँ: https://cses.fi/problemset/task/1144/

200000तत्वों तक की एक सरणी को देखते हुए , मेरा कार्य 200000प्रश्नों पर प्रक्रिया करना है , जो या तो मुझे सरणी के भीतर एक एकल मान अपडेट करने के लिए कहते हैं या मुझे दिए गए सीमा में a और b के बीच तत्वों की संख्या ज्ञात करने के लिए कहते हैं (के लिए) उदाहरण के लिए, एक प्रश्न के सूचकांक से कई तत्वों कैसे पूछना होगा 1करने के लिए 5श्रेणी में हैं [2, 3])।

मेरा वर्तमान विचार पहले दिए गए सरणी में मूल्यों पर सूचकांक संपीड़न का उपयोग करना है (चूंकि मान ऊपर हो सकते हैं 10^9, इसलिए एक साधारण घटना सरणी रखने से भंडारण सीमाएं पार हो जाएंगी), फिर एक और सरणी रखें जिसमें प्रत्येक संपीडित की घटनाओं की संख्या हो। संख्या। फिर, एक सेगमेंट ट्री का उपयोग करके प्रोसेसिंग और अपडेटिंग क्वेरी की जा सकती है।

हालांकि, मैं इस दृष्टिकोण को लागू करने की कोशिश करते समय एक समस्या में भाग गया। मुझे एहसास हुआ कि एकल सरणी मान को अपडेट करने से मुझे संकुचित सरणी को बदलने के लिए मजबूर होना पड़ेगा।

उदाहरण के लिए, एक सरणी को देखते हुए [1, 5, 3, 3, 2], मैं Cइस तरह के एक संपीड़न फ़ंक्शन को परिभाषित करूंगा

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;

फिर, घटना सरणी होगी [1, 1, 2, 1], और समसामयिकी प्रसंस्करण कुशल होगा। हालाँकि, अगर मुझे एक वैल्यू अपडेट करने के निर्देश दिए गए थे, तो कहें कि तीसरे तत्व को बदल दें 4, फिर वह सब कुछ संतुलन से बाहर फेंक देगा। संपीड़न फ़ंक्शन को बदलना होगा

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;

जो मुझे अपनी घटना सरणी को फिर से संगठित करने के लिए मजबूर करेगा, जिसके परिणामस्वरूप O(N)अद्यतन समय होगा।

चूंकि Nतक हो सकता है 200000, मेरे वर्तमान दृष्टिकोण कुशलता से समस्या को हल करने के लिए पर्याप्त काम नहीं करेगा, हालांकि मुझे लगता है कि मैं सूचकांक संपीड़न के साथ सही विचार है। क्या कोई मुझे मेरी विधि के साथ सही दिशा में इंगित कर सकता है?

Answer 1

इंडेक्स कम्प्रेशन - बढ़िया सोच का उपयोग करने में आपके पास सही विचार है! जैसा Nकि केवल होता है 200000, एरेस सरणी रखने के 200000बजाय दिए गए सरणी के प्रारंभिक मानों के लिए तत्वों की आवश्यकता होगी 10^9।

स्वयं के अनुसार, समस्या का सामना तब होता है जब आप प्रसंस्करण क्वेरी के दौरान नए मूल्यों का सामना करते हैं। आप सही हे; यह O(N)समय-समय पर चलने के लिए घटना सरणी को बंद-संतुलन और अद्यतन को फेंक देगा । इस समस्या का समाधान आपके वर्तमान तरीके के लिए एक छोटा संशोधन है।

नए मूल्यों का सामना करने की समस्या को हल करने के लिए, हम बस यह सुनिश्चित कर सकते हैं कि हम कभी भी नए मूल्यों का सामना नहीं करेंगे । हम योग खंड वृक्ष के निर्माण से पहले सभी प्रश्नों को पढ़कर ऐसा कर सकते हैं । यह अधिकतम N + 2*Qअद्वितीय मूल्यों या 600000सबसे खराब स्थिति में परिणाम देगा , जो समस्या की 512MB भंडारण सीमा के साथ एक घटना सरणी का निर्माण करने के लिए पर्याप्त है। उसके बाद, एक योग खंड वृक्ष इन प्रश्नों का उत्तर कुशलता से दे सकेगा।

इसलिए अंत में, इस समस्या को हल करने के लिए एक रणनीति होगी कि हर यूनिक नंबर को इनपुट किया जाए, फिर एक इंडेक्स कम्प्रेशन फंक्शन का निर्माण किया जाए, फिर एक सेगमेंट ट्री को कुशलतापूर्वक सम क्वेश्चन प्रोसेस करने के लिए उपयोग करें।

भविष्य में, याद रखें कि क्वेरी-उत्तर देने वाले प्रश्नों के इन प्रकारों में, प्री-कम्यूटेशन से पहले सभी इनपुट में पढ़ना उपयोगी हो सकता है । अपने कार्यक्रम के साथ शुभकामनाएँ।

Answer 2

पहले, भोले पर विचार करें: प्रत्येक अद्यतन के लिए, सरणी को अपडेट करें। प्रत्येक क्वेरी के लिए, पूरे ऐरे से स्कैन करें और अपना उत्तर एकत्र करें। इस समाधान की जटिलता में O(n)अपडेट, O(n)क्वेरीज़ हैं। अच्छा नहीं।

हम यकीनन बदतर समय जटिलता के साथ एक अलग समाधान के साथ आ सकते हैं, लेकिन यह हमें एक संकेत देता है कि हमारा अंतिम परिणाम क्या है। स्रोत सरणी को हर समय बनाए रखें, लेकिन मूल्य-> आवृत्ति का हैश मानचित्र भी रखें। फिर, जब आप अपडेट करते हैं, तो पुराने मूल्य पर आवृत्ति को घटाएँ और इसे नए मूल्य पर बढ़ाएँ। अब, क्वेरी के लिए, उस क्वेरी रेंज के सभी मूल्यों के माध्यम से लूप करें और उन्हें अपने उत्तर के लिए योग करें। इससे O(1)अपडेट और O(r-l)क्वेरीज़ प्राप्त होती हैं, इसलिए हमारे पास बहुत अच्छे अपडेट हैं लेकिन भयानक क्वेरीज़ हैं। हालांकि, इस परिणाम अगर हम कर सकते हैं पर सुधार किया जा सकता है सिर्फ उन प्रश्नों को गति! सेगमेंट ट्री दर्ज करें ।

परंपरागत रूप से, आप निर्माण पर इसके पत्तों के नीचे एक सेगमेंट ट्री का निर्माण करेंगे। हालाँकि, हम मुख्य रूप से एक सेगमेंट ट्री की तरह होते हैं 0-10^9, जो वहाँ से होता है , इसलिए इसका कोई तरीका नहीं है कि हम इतनी मेमोरी उत्पन्न कर सकें (और ऐसा करने में हमारा समय निकल जाए)। हालाँकि, क्या होगा अगर हम एक सेगमेंट ट्री बनाते हैं, लेकिन हर नोड के लिए, इसके बच्चों को निहित किया जाता है यदि उनका उपयोग कभी नहीं किया गया हो। यदि उनमें तत्व नहीं हैं , तो बाल नोड्स न बनाएं । इस संरचना को नाम दिया गया है, उपयुक्त, इम्प्लिक्ट सेगमेंट ट्री। यहां विचार आपके खंड के पेड़ को सामान्य के रूप में लागू कर रहा है सिवाय निर्माणकर्ता के उस हिस्से को छोड़ दें जहां आप अपने बाएं और दाएं बच्चों को शुरू करते हैं। अब, जब आपको एक आंशिक श्रेणी क्वेरी के कारण अपने बच्चों में तल्लीन करने की आवश्यकता होती है, तो जांचें कि क्या वे मौजूद हैं, और यदि वे नहीं हैं, तो उन्हें बनाएं। अन्यथा, जब से आपको उन्हें बनाने की आवश्यकता नहीं है, मान लें कि उन नोड्स में मानों का योग 0 है!

अंतिम समाधान इस प्रकार है: अधिकतम मान क्वेरी का एक सेगमेंट ट्री बनाएं (यदि आपको अंतःक्रियात्मक रूप से उत्तर देने की आवश्यकता नहीं है, तो अधिकतम आर-मान प्राप्त करने के लिए अपने प्रश्नों को सहेजने और स्कैन करने पर विचार करें, लेकिन आपके पास नहीं है)। यह एक निहित खंड पेड़ बनाने के लिए ध्यान दें । हर अपडेट के बाद सोर्स एरे को बनाए रखें, और अपने ट्री पर पॉइंट-अपडेट भी करें जो कि होगा O(log(max value))। प्रश्न नियमित खंड ट्री रेंज प्रश्न हैं, इसलिए ये होंगे O(log(max value))। और वहाँ यह है!

Answer 3

आप नीति आधारित डेटा संरचना का उपयोग कर सकते हैं, जिसमें कुछ उपयोगी विधियाँ हैं जैसे कि order_of_key () - जो दी गई संख्या से कम वस्तुओं की संख्या लौटाती है। हम इसे दो बार getcnt (b + 1) - getcnt (a) की तरह कह सकते हैं - जो दी गई श्रेणी के बीच वस्तुओं की गिनती देता है। इस पर अधिक जानकारी के लिए - आप उल्लेख कर सकते हैं -https://codeforces.com/blog/entry/11080 और भी https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html

बहुत शोध के बाद मैंने पाया कि पेड़ आधारित संरचनाओं का उपयोग करते समय यह एसटीएल बहुत उपयोगी है।

मैंने नीचे दिए गए कोड का परीक्षण किया और यह सभी परीक्षण मामलों को पास करता है।

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
 
using namespace std;
using namespace __gnu_pbds;
 
template<class T> using cust_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
cust_set<array<int,2>> freq;
 
int getcnt(int x)
{
    return freq.order_of_key({x,0});
}
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    vector<int> emp(n);
    
    int sal;
    for(int i=0;i<n;i++)
    {
        cin >> emp[i];
        freq.insert({emp[i],i});
    }
    char c;
    int x,a,b;
    while(q--)
    {
        cin>> c;
        int ans=0;
        if(c=='?')
        {
            cin>>a>>b;
            cout << getcnt(b+1) - getcnt(a)<<"\n";
        }
        else
        {
            cin>>a>>b;
            --a;
            freq.erase({emp[a],a});
            emp[a] = b;
            freq.insert({emp[a],a});
        }
    }
    return 0;
}