ចំនួនធាតុតិចជាងឬស្មើទៅនឹងចំនួនដែលបានផ្តល់ឱ្យនៅក្នុងសញ្ញារងដែលបានផ្តល់ឱ្យ


កម្រិតលំបាក រឹង
សួរញឹកញាប់ លេខកូដ DE Shaw ក្រុមហ៊ុន google ល្ខោនអូប៉េរ៉ា បានតាមរយៈការ Pinterest
អារេ មែកធាង

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ ចំនួនធាតុតិចជាងឬស្មើទៅនឹងចំនួនដែលបានផ្តល់ឱ្យក្នុងដែនដីរងដែលបានផ្តល់ឱ្យ” ចែងថាអ្នកត្រូវបានផ្តល់អារេចំនួនគត់និង q ចំនួនសំណួរ។ នឹងមានសំណួរពីរប្រភេទà

  • queryUpdate (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

ការពន្យល់

queryPrint (០, ២, ២) នឹងបោះពុម្ពចំនួនធាតុតិចជាងឬស្មើ ២ ពីសន្ទស្សន៍ ០ ដល់ ២ ពោលគឺ ១

queryUpdate (២, ៨) នឹងធ្វើបច្ចុប្បន្នភាពធាតុនៅលិបិក្រម ២ ជាមួយតម្លៃ ៨ ឧ។ ការមកដល់នឹងមាន {២, ៤, ៨, ១, ៥}

queryPrint (០, ២, ២) នឹងបោះពុម្ពចំនួនធាតុតិចជាងឬស្មើ ២ ពីសន្ទស្សន៍ ០ ដល់ ២ ពោលគឺ ១

queryUpdate (៤, ៣) នឹងធ្វើបច្ចុប្បន្នភាពធាតុនៅលិបិក្រម ៤ ជាមួយ ៣ ឧ។ ការមកដល់នឹងមាន {២, ៤, ៨, ១, ៣}

queryUpdate (៤, ៣) នឹងធ្វើបច្ចុប្បន្នភាពធាតុនៅលិបិក្រម ៤ ជាមួយ ៣ ឧ។ ការមកដល់នឹងមាន {២, ៤, ៨, ១, ៣}

queryPrint (០, ២, ២) នឹងបោះពុម្ពចំនួនធាតុតិចជាងឬស្មើ ២ ពីសន្ទស្សន៍ ០ ដល់ ២ ពោលគឺ ១

ចំនួនធាតុតិចជាងឬស្មើទៅនឹងចំនួនដែលបានផ្តល់ឱ្យនៅក្នុងសញ្ញារងដែលបានផ្តល់ឱ្យ

 

ក្បួនដោះស្រាយសម្រាប់ការស្វែងរកលេខ <= គុណតម្លៃដែលបានផ្តល់ជាអនុគម

  1. ចែក អារេ ចូលទៅក្នុងប្លុកនៃទំហំស្មើនឹងឫសការ៉េនៃ n ដែល n ជាទំហំនៃអារេបញ្ចូល។
  2. បង្កើតមែកធាងសន្ទស្សន៍គោលពីរដែលមានទំហំធំជាងធាតុអតិបរមាដែលមាននៅក្នុងអារេនៅក្នុងប្លុកជាក់លាក់មួយ។
  3. ស្វែងយល់ពីប្លុកសម្រាប់ធាតុនីមួយៗនៃអារេទៅកន្លែងដែលវាជាកម្មសិទ្ធិហើយធ្វើបច្ចុប្បន្នភាពអារេប៊ីតរបស់ប្លុកជាមួយនឹងលេខ 1 នៅព្រី [ខ្ញុំ] ។
  4. សម្រាប់សំណួរបច្ចុប្បន្នភាពនីមួយៗ។ ធ្វើឱ្យទាន់សម័យតម្លៃនៃអារេប៊ី, ទាក់ទងទៅនឹងប្លុកនៅតម្លៃដើមនៃអារេសម្រាប់សន្ទស្សន៍ជាមួយ -1 ។
  5. ធ្វើបច្ចុប្បន្នភាពអារេប៊ីតប្លុកដូចគ្នាជាមួយនឹងតម្លៃ 1 នៅធាតុថ្មីនៃសន្ទស្សន៍ជាក់លាក់។
  6. សម្រាប់សំណួរបោះពុម្ពនីមួយៗ។ ធ្វើសំណួរទៅអារេប៊ីធីដើម្បីរាប់តម្លៃធាតុតិចជាងឬស្មើ k ។ ហើយសម្រាប់ប្លុកពេញលេញឬសម្រាប់ប្លុកមិនពេញលេញឬដោយផ្នែកឆ្លងកាត់ឆ្លងកាត់ធាតុទាំងអស់។

ការពន្យល់

យើងត្រូវបានផ្តល់អារេចំនួនគត់និងសំណួរពីរប្រភេទ។ សំណួរមួយគឺត្រូវធ្វើបច្ចុប្បន្នភាពតម្លៃនៅសន្ទស្សន៍ជាក់លាក់មួយ។ ហើយសំណួរមួយទៀតគឺត្រូវរាប់ចំនួនធាតុតិចជាង k ។ សម្រាប់សំណួរបច្ចុប្បន្នភាពយើងនឹងត្រូវបានផ្តល់សន្ទស្សន៍និងតម្លៃ។ យើងនឹងធ្វើបច្ចុប្បន្នភាពតម្លៃ v នៅសន្ទស្សន៍ដែលបានផ្តល់អារេ [i] ។ ចំពោះសំណួរបោះពុម្ពឬរាប់សំណួរយើងត្រូវបោះពុម្ពចំនួនគត់ដែលតូចជាងឬស្មើ k ។

យើងនឹងចែកអារេទៅជាប្លុកមួយចំនួន។ ប្លុកទាំងនេះនឹងមានទំហំដូចជាឫសការ៉េនៃប្រវែងរបស់អារេ។ សម្រាប់រាល់ប្លុកយើងនឹងត្រូវបានថែរក្សាក មែកធាងសន្ទស្សន៍គោលពីរ។ ទំហំនៃមែកធាងសន្ទស្សន៍គោលពីរនឹងជាធាតុមួយច្រើនជាងធាតុអតិបរិមាសម្រាប់ប្លុកជាក់លាក់មួយនៃធាតុអារេ។ ដោយសារយើងមានអារេប៊ីតសម្រាប់ប្លុកនីមួយៗធ្វើបច្ចុប្បន្នភាពអារេប៊ីតតម្លៃជាមួយតម្លៃទី ១ នៅទីតាំងនីមួយៗនៃអារេ [i] ហើយក៏រកឃើញប្លុកសម្រាប់ធាតុនីមួយៗនៃអារេទៅកន្លែងដែលវាជាកម្មសិទ្ធិហើយអនុវត្តតាមនីតិវិធីដូចខាងលើ។ ធ្វើឱ្យទាន់សម័យអារេបន្តិចនៃប្លុកនោះជាមួយ 1 នៅព្រី [ខ្ញុំ] ។

សម្រាប់សំណួរធ្វើបច្ចុប្បន្នភាពនីមួយៗធ្វើបច្ចុប្បន្នភាពអារេប៊ីត។ ចាប់តាំងពីយើងមានប្លុកសម្រាប់ធាតុអារេនីមួយៗ។ ធ្វើបច្ចុប្បន្នភាពតម្លៃនៃអារេនៅសន្ទស្សន៍ជាក់លាក់មួយជាមួយតម្លៃ -1 និងធ្វើបច្ចុប្បន្នភាពអារេប៊ីតប្លុកដែលត្រូវការជាមួយតម្លៃ 1 នៅធាតុថ្មីនៃអារេនៅសន្ទស្សន៍ដែលបានផ្តល់ឱ្យ។ ហើយសម្រាប់សំណួរនៃការបោះពុម្ពឬរាប់តម្លៃគ្រាន់តែឆ្លងកាត់រង្វិលជុំ។ វានឹងមានករណីពីរដែលសម្រាប់ប្លុកពេញលេញឬសម្រាប់ប្លុកពេញលេញដោយផ្នែក។ នៅពេលត្រឡប់មកវិញតម្លៃ។

លេខកូដ

លេខកូដ C ++ សម្រាប់រកលេខ <= តម្លៃដែលបានផ្តល់ជាអនុគម

#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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

ឱ (១) សម្រាប់ធ្វើបច្ចុប្បន្នភាពអារេនិង អូរ (n) សម្រាប់ការបោះពុម្ពអារេ។

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ បញ្ហា“ ចំនួនធាតុតិចជាងឬស្មើនឹងលេខដែលបានផ្តល់ឱ្យនៅក្នុងអនុដ្ឋានដែលបានផ្តល់ឱ្យ” មានទំហំលីនេអ៊ែរ។