ڏنل مضمونن ۾ ڏنل تعداد کان گهٽ يا برابر جو تعداد


تڪليف جي سطح سخت
بار بار پڇڻ ۾ ڪوڊشن ڊي شاه گوگل ناٽڪ PayPal Pinterest
ڪيريو وڻن

مسئلي جو بيان

مسئلو "عنصرن جو تعداد هڪ ڏنل سبريڊي ۾ ڏنل تعداد کان گهٽ يا برابر برابر آهي" ٻڌائي ٿو ته توهان کي سوالن جي انگيري صف ۽ ق تعداد ڏني وئي آهي سوالن جا ٻه قسم هوندا à

  • queryUpdate (i ، v): هتي ٻه انٽگرس آئي ۽ وي هوندا ، اهڙي طرح جيڪو آرٽ کي اپڊيٽ ڪندو [i] = v.
  • queryPrint (کاٻي ، سا rightي ، ڪ): ڇپيل انگ جي عدد اندران حد جيڪا ڪي جي برابر کان گهٽ هجي.

مثال

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

وضاحت

queryPrint (0 ، 2 ، 2) پرنٽ 2 کان 0 تائين 2 کان گهٽ يا برابر جي عنصرن جي تعداد کي پرنٽ ڪندو يعني 1

queryUpdate (2 ، 8) ايٽمي نمبر 2 ۾ عنصر 8 جي قدر سان تازه ڪاري ڪندو يعني arr ٿي ويندي {2، 4، 8، 1، 5}

queryPrint (1 ، 3 ، 5) پرنٽ 5 کان 1 تائين 3 کان گهٽ يا برابر جي عنصرن جي تعداد کي پرنٽ ڪندو يعني 2

queryUpdate (4 ، 3) انڊيڪس 4 تي عنصر کي 3 سان اپڊيٽ ڪندو يعني arr ٿي ويندو {2، 4، 8، 1، 3}

queryUpdate (1 ، 3) انڊيڪس 1 تي عنصر کي 3 سان اپڊيٽ ڪندو يعني arr ٿي ويندو {2، 3، 8، 1، 3}

queryPrint (1 ، 2 ، 4) پرنٽ 4 کان 1 تائين 2 کان گهٽ يا برابر جي عنصرن جي تعداد کي پرنٽ ڪندو يعني 1

ڏنل مضمونن ۾ ڏنل تعداد کان گهٽ يا برابر جو تعداد

 

الگورٿم کي ڳولهڻ لاءِ نمبر = = ڏنل قيمت ۾ ڏنل قدر

  1. ورهايو صف n جي چورس روٽ جي برابر ماپ جي بلاڪ ۾ ، جتي n انپٽ صف جي ماپ آهي.
  2. ھڪڙي بلاڪ ۾ موجود ھڪڙي کان وڌيڪ عنصر ٺاھڻ جي ھڪڙي کان وڌيڪ ھڪڙي بائنري انڊيڪس وڻ ٺاھيو.
  3. صف جي هر عنصر لاءِ بلاڪ کي ڳوليو اهو ڪهڙي جڳهه سان آهي ۽ 1 تي arr [i] سان بلاڪ جي بي آءِ ٽي صف کي اپڊيٽ ڪريو.
  4. هر تازه ڪاري سوال لاءِ. BIT صف جي قيمت کي تازو ڪريو ، بلاڪ جي اصلي قيمت تي آرٽيڪل جي اصلي قيمت تي -1 سان.
  5. هڪ خاص انڊيڪس جي نئين عنصر تي 1 جي ساڳي بلاڪ جي بي آءِ ٽي صف کي تازه ڪاري ڪريو.
  6. هر ڇاپي لاءِ. BIT صف ڏانهن پڇاڻو ڪريو ، عناصر جي قيمت کي ڪ يا ان کان برابر جي ڳڻپ ڪرڻ لاءِ. ۽ مڪمل رڪاوٽ لاءِ يا نامڪمل يا جزوي بلاڪ لاءِ ، مڙني عنصرن تان گذري.

وضاحت

اسان کي هڪ انڌي سِر ۽ ٻن قسمن جي سوالن ڏني وئي آهي. ھڪڙي سوال ڏنل ھڪڙي خاص انڊيڪس ۾ قيمت کي تازه ڪاري ڪرڻ آھي. ۽ هڪ ٻيو سوال ڪي جي برابر عنصرن جي ڳڻپ حاصل ڪرڻ آهي. اپڊيٽ سوال جي لاءِ ، اسان کي هڪ انڊيڪس ۽ هڪ قدر ڏنو ويندو. اسان قدر کي تازو ڪنداسين v صف جي ڏنل انڊيڪس تي [i]. ڇاپڻ واري سوال يا ڳڻپ جي سوال لاءِ ، اسان کي انٽيگرز جي تعداد کي پرنٽ ڪرڻ جي ضرورت آهي ، جيڪي ڪ کان گهٽ يا برابر آهن.

اسان صف کي ڪجهه بلاڪ ۾ ورهائڻ وارا آهيون. اهي بلاڪ هڪ جيتري ٿين ٿا جيئن صف جي ڊيگهه جي مربع روٽ. هر بلاڪ لاءِ ، اسان برقرار رکنداسين هڪ بائنري انڊيڪس وڻ. بائنري انڊيڪس وڻ جو اندازو ، ھڪڙو صفري عنصر جي ھڪڙي بلاڪ لاءِ وڌ کان وڌ عنصر کان وڌيڪ ٿيندو. ڇاڪاڻ ته اسان وٽ هر بلاڪ لاءِ BIT صف آهي ، صف جي هر پوزيشن تي 1 جي قيمت سان لڳل بٽ جي ترتيب کي اپڊيٽ ڪريو [۽] ۽ پڻ صف جي هر عنصر لاءِ بلاڪ ڳوليو جتي اهو تعلق رکي ٿو ۽ ساڳئي طريقي سان مٿي followاڻايل طريقي تي عمل ڪيو. انهي بلاڪ جي بٽ صف کي اپڊيٽ ڪريو 1 تي arr [i] سان.

هر تازه ڪاري سوال لاءِ ، BIT صف کي تازو ڪريو. جئين اسان وٽ هر صف جي عنصر لاءِ بلاڪ آهي. صف واري قيمت کي خاص انڊيڪس ۾ قدر -1 سان تازه ڪاري ڪريو ۽ گهربل بلاڪ جي بي آئي ٽي صف کي تازه ڪاري ڪريو. ۽ پرنٽ جي سوال يا قدرن جي ڳڻپ لاءِ ، صرف لڙائيءَ کان گذري. اتي ٻه ڪيس هوندا جيڪي پوري بلاڪ لاءِ يا جزوي طور مڪمل بلاڪ لاءِ. آخر ۾ قيمت وڃايو.

ڪوڊ

نمبر ڳولڻ لاءِ سي ++ ڪوڊ <= سبار ۾ ڏنل قدر

#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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (1) صف کي تازو ڪرڻ لاءِ ۽ اي (ن) صف کي ڇپائڻ لاءِ.

خلائي پيچيدگي

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي. مسئلو "عنصرن جو تعداد گهٽ يا هڪ جيتري قدر هڪ ڏنل سبيل ۾" برابر آهي لڪير واري جڳهه.