दिइएको subarray मा दिइएको संख्या भन्दा कम वा बराबर तत्त्वहरूको संख्या  


कठिनाई तह हार्ड
बारम्बार सोधिन्छ CodeNation डे श गुगल ओपेरा PayPal Pinterest
एरे ट्री

समस्या वक्तव्य  

समस्या "दिइएको subarray मा दिइएको संख्या भन्दा कम वा बराबर तत्त्वहरूको संख्या" बताउँछ कि तपाईंलाई पूर्णांक एरे र प्रश्नहरूको Q संख्या दिइन्छ। जिज्ञासाहरू दुई प्रकारका हुनेछन्

  • क्वेरीअपडेट (i, v): त्यहाँ दुई पूर्णा .्कहरू i र v हुनेछन्, जसले एरे अपडेट गर्दछ [i] = v।
  • क्वेरीप्रिन्ट (बाँया, दाँया, के): दायरा भित्रको पूर्णांक संख्या प्रिन्ट गर्नुहोस् जुन k सँग बराबर भन्दा कम छ।

उदाहरणका  

arr[]={2, 4, 6, 1, 5)
queryPrint(0, 2, 2)
queryUpdate(2, 8)
queryPrint(1, 3, 5)
queryUpdate(4, 3)
queryUpdate(1, 3)
queryPrint(1, 2, 4)
1 2 1

स्पष्टीकरण

क्वेरीप्रिनेट (०, २, २) ० भन्दा कम वा बराबर to तत्वहरूको संख्या प्रिन्ट गर्दछ ० ० देखि २ सम्म, १

क्वेरीUpdate (२,)) element मानको साथ अनुक्रमणिका २ मा तत्व अपडेट गर्दछ जस्तै एआर {२,,,,, १,} will हुनेछ

क्वेरीप्रिनेट (०, २, २) ० भन्दा कम वा बराबर to तत्वहरूको संख्या प्रिन्ट गर्दछ ० ० देखि २ सम्म, १

क्वेरीUpdate (,,)) element को साथ सूचकांक at मा तत्व अपडेट गर्दछ अर्थात् अर {२,,,,, १,} will हुनेछ

क्वेरीUpdate (,,)) element को साथ सूचकांक at मा तत्व अपडेट गर्दछ अर्थात् अर {२,,,,, १,} will हुनेछ

क्वेरीप्रिनेट (०, २, २) ० भन्दा कम वा बराबर to तत्वहरूको संख्या प्रिन्ट गर्दछ ० ० देखि २ सम्म, १

दिइएको subarray मा दिइएको संख्या भन्दा कम वा बराबर तत्त्वहरूको संख्यापिन

 

संख्याहरू फेला पार्नको लागि एल्गोरिथ्म <= सब्रेमा मान दिइएको  

  1. विभाजन गर्नुहोस् array n को वर्गमूलको बराबर आकारको ब्लकमा, जहाँ n इनपुट एरेको आकार हो।
  2. एक विशेष ब्लकमा एर्रेमा उपस्थित अधिकतम तत्व भन्दा बढि आकारको बाइनरी अनुक्रमणिका रूख बनाउनुहोस्।
  3. एर्रेको प्रत्येक एलिमेन्टको लागि ब्लक पत्ता लगाउनुहोस् जहाँ यो सम्बन्धित छ र ब्लकको BIT एर्रे अपडेट गर्नुहोस् एरमा १ सँग [i]।
  4. प्रत्येक अपडेट क्वेरीको लागि। BIT एर्रेको मान अपडेट गर्नुहोस्, -१ को साथ अनुक्रमणिकाको लागि एरेको मूल मानमा ब्लकको सापेक्ष।
  5. विशेष सूचकांकको नयाँ एलिमेन्टमा समान १ ब्लकको BIT एर्रे अपडेट गर्नुहोस्।
  6. प्रत्येक प्रिन्ट क्वेरीका लागि। KIT भन्दा कम वा बराबर मानहरूको गणना गर्न BIT एर्रेमा क्वेरी गर्नुहोस्। र पूर्ण ब्लक को लागी वा अपूर्ण वा आंशिक ब्लक को लागी, सबै तत्वहरु को माध्यम बाट पार।
पनि हेर्नुहोस्
एर्रेमा दिइएको अनुक्रमणिका दायराहरूको GCDs

स्पष्टीकरण

हामीलाई पूर्णांक एरे र दुई प्रकारका प्रश्नहरू दिइन्छ। एउटा क्वेरी भनेको विशेष ईन्डेक्समा मान अपडेट गर्नु हो। र अर्को क्वेरी भनेको केबल बराबर भन्दा कम तत्वहरूको गणना प्राप्त गर्नु हो। अपडेट क्वेरीको लागि, हामीलाई एउटा अनुक्रमणिका र मान दिइनेछ। हामी मान अपडेट गर्नेछौं v एरेको दिइएको सूचकमा [i]। प्रिन्ट क्वेरी वा काउन्ट क्वेरीका लागि, हामीले पूर्णांकको संख्या प्रिन्ट गर्नु पर्छ, जुन k भन्दा कम वा बराबर हुन्छ।

हामी एर्रेलाई केही ब्लकमा विभाजन गर्न जानेछौं। यी ब्लकहरू आकारको एरेको लम्बाइको वर्गमूलको रूपमा हुनेछन्। हरेक ब्लक को लागी, हामी एक को रखरखाव हुनेछ बाइनरी अनुक्रमणिका रूख। बाइनरी अनुक्रमणिका रूखको आकार एरे एलिमेन्टको विशेष खण्डका लागि अधिकतम तत्त्व भन्दा बढि एक हुनेछ। किनकि हामीसँग प्रत्येक ब्लकको लागि BIT एर्रे छ, एरेको प्रत्येक स्थितिमा मान १ को साथ मान बिट एर्रे अपडेट गर्नुहोस् [i] र साथै एर्रेको प्रत्येक एलिमेन्टको लागि ब्लक पत्ता लगाउनुहोस् र माथिको जस्तै प्रक्रिया अनुसरण गर्नुहोस्। अवरमा १ सँग ब्रोकको बिट एर्रे अपडेट गर्नुहोस् [i]।

प्रत्येक अपडेट क्वेरीको लागि, BIT एर्रे अपडेट गर्नुहोस्। हामीसँग प्रत्येक एर्रे एलिमेन्टको लागि ब्लक छ। कुनै विशेष सूचकांकमा एरेको मान -१ को साथ अद्यावधिक गर्नुहोस् र दिइएको ब्ल्याकको BIT एर्रे अद्यावधिक गर्नुहोस् दिइएको अनुक्रमणिकामा एरेको नयाँ एलिमेन्टमा मान १ सँग। र प्रिन्टको क्वेरीको लागि वा मान गणना गर्नुहोस्, लूपको माध्यमबाट मात्र पार गर्नुहोस्। त्यहाँ दुईवटा केसहरू छन् जुन पूर्ण ब्लकको लागि वा आंशिक पूर्ण ब्लकको लागि हो। अन्तिम फिर्तामा मान।

पनि हेर्नुहोस्
अधिकतम बाइनरी रूख

कोड  

C ++ कोड खोज्न को लागी संख्या <= subarray मा दिइएको मान

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>

using namespace std;

const int MAX = 10001;

void update(int index, int block, int val, int bit[][MAX])
{
    for (; index < MAX ; index += (index&-index))
        bit[block][index] += val;
}
int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][MAX])
{
    int sum = 0;
    while (left<right && left%blockSize!=0 && left!=0)
    {
        if (arr[left] <= k)
            sum++;
        left++;
    }

    while (left + blockSize <= right)
    {
        int index = k;
        for (; index > 0 ; index -= index&-index)
            sum += bit[left/blockSize][index];
        left += blockSize;
    }

    while (left <= right)
    {
        if (arr[left] <= k)
            sum++;
        left++;
    }
    return sum;
}
void preprocess(int arr[], int blockSize, int n, int bit[][MAX])
{
    for (int i=0; i<n; i++)
        update(arr[i], i/blockSize, 1, bit);
}

void queryUpdate(int i, int v, int blockSize,int arr[], int bit[][MAX])
{
    update(arr[i], i/blockSize, -1, bit);
    update(v, i/blockSize, 1, bit);
    arr[i] = v;
}
int main()
{
    int arr[] = {2,4,6,1,5};
    int n = sizeof(arr)/sizeof(arr[0]);

    int blockSize = sqrt(n);

    int bit[blockSize+1][MAX];

    memset(bit, 0, sizeof(bit));

    preprocess(arr, blockSize, n, bit);

    cout << queryPrint (0, 2, 2, arr, blockSize, bit) << endl;

    queryUpdate(2, 8, blockSize, arr, bit);

    cout << queryPrint(1, 3, 5, arr, blockSize, bit) << endl;

    queryUpdate(4, 3, blockSize, arr, bit);

    queryUpdate(1, 3, blockSize, arr, bit);

    cout << queryPrint (1, 2, 4, arr, blockSize, bit) << endl;
    return 0;
}
1
2
1

जाभा कोड खोज्नका लागि संख्याहरू = = सबभरमा दिइएको मान

class NumberElements
{
    static final int MAX = 10001;

    static void update(int index, int block, int val, int bit[][])
    {
        for ( ; index < MAX ; index += (index&-index))
            bit[block][index] += val;
    }
    static int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][])
    {
        int sum = 0;
        while (left < right && left % blockSize != 0 && left != 0)
        {
            if (arr[left] <= k)
                sum++;
            left++;
        }
        while (left + blockSize <= right)
        {
            int index = k;
            for (; index > 0 ; index -= index&-index)
                sum += bit[left/blockSize][index];
            left += blockSize;
        }
        while (left <= right)
        {
            if (arr[left] <= k)
                sum++;
            left++;
        }
        return sum;
    }
    static void buildArray(int arr[], int blockSize, int n, int bit[][])
    {
        for (int i=0; i<n; i++)
            update(arr[i], i/blockSize, 1, bit);
    }

    static void queryUpdate(int i, int v, int blockSize, int arr[], int bit[][])
    {
        update(arr[i], i/blockSize, -1, bit);
        update(v, i/blockSize, 1, bit);
        arr[i] = v;
    }

    public static void main(String args[])
    {
        int arr[] = {2,4,6,1,5};

        int blockSize = (int) Math.sqrt(arr.length);

        int bit[][] = new int[blockSize+1][MAX];
        buildArray(arr, blockSize, arr.length, bit);

        System.out.println(queryPrint(0, 2, 2, arr, blockSize, bit));

        queryUpdate(2, 8, blockSize, arr, bit);

        System.out.println(queryPrint(1, 3, 5, arr, blockSize, bit));

        queryUpdate(4, 3, blockSize, arr, bit);

        queryUpdate(1, 3, blockSize, arr, bit);

        System.out.println(queryPrint (1, 2, 4, arr, blockSize, bit));

    }
}
1
2
1

जटिलता विश्लेषण  

समय जटिलता

O (१) एर्रे अपडेट गर्नका लागि र ऊ) एर्रे प्रिन्ट गर्नका लागि।

पनि हेर्नुहोस्
बाइनरी रूखमा मेटाउने

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। समस्या "तत्वहरूको संख्या कम वा दिइएको दिइएको subarray मा दिइएको संख्या बराबर" लाईन स्पेस छ।