បោះពុម្ពអារេដែលបានកែប្រែបន្ទាប់ពីប្រតិបត្តិពាក្យបញ្ជាបន្ថែមនិងដក


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ByteDance ស៊ីស្កូ Citrix FreeCharge HackerRank ណាហ្គារ៉ូ ល្ខោនអូប៉េរ៉ា តេរ៉ាតាតា
អារេ

អ្នកត្រូវបានផ្តល់ទំហំអារេ n ដំបូងតម្លៃទាំងអស់នៅក្នុងអារេនឹងមាន ០ និងសំណួរ។ សំណួរនីមួយៗមានតម្លៃ ៤ ប្រភេទគឺប្រភេទសំណួរ T ចំណុចខាងឆ្វេងនៃជួរចំណុចខាងស្តាំនៃជួរនិងលេខ k អ្នកត្រូវអនុវត្តប្រតិបត្តិការដូចខាងក្រោម។

ប្រសិនបើ T = 0 បន្ថែមតម្លៃ k ទៅចំនួនគត់ទាំងអស់នៅក្នុងជួរដែលបានផ្តល់ (ចាប់ផ្តើម, បញ្ចប់) នៅក្នុងអារេដែលបានផ្តល់,

ប្រសិនបើ T = 1 ដកតម្លៃ k ពីចំនួនគត់ទាំងអស់នៅក្នុងជួរដែលបានផ្តល់ (ចាប់ផ្តើម, បញ្ចប់) នៅក្នុងអារេដែលបានផ្តល់,

ឧទាហរណ៍

arr[]={0, 0, 0, 0, 0}
Query: {(0, 2, 4, 1), (1, 3, 5, 2), (0, 1, 4, 3)}
3 4 2 2 -2

ការពន្យល់

(០, ២, ៤, ១) បន្ថែម ១ ដល់ចំនួនគត់ទាំងអស់ក្នុងជួរព្រោះវាជាប្រភេទសំណួរ ០ ។

(១, ៣, ៥, ២) ដក ២ ពីចំនួនគត់ទាំងអស់នៅក្នុងជួរព្រោះវាជាប្រភេទសំណួរ ១ ។

(០, ២, ៤, ១) បន្ថែម ១ ដល់ចំនួនគត់ទាំងអស់ក្នុងជួរព្រោះវាជាប្រភេទសំណួរ ០ ។

បោះពុម្ពអារេដែលបានកែប្រែបន្ទាប់ពីប្រតិបត្តិពាក្យបញ្ជាបន្ថែមនិងដក

 

ក្បួនដោះស្រាយដើម្បីបោះពុម្ពអារេដែលបានកែប្រែបន្ទាប់ពីមានសំណួរច្រើន

  1. ចាប់ផ្តើមឯកសារ អារេ ជាមួយ ៣៣៣ ។
  2. សម្រាប់សំណួរនីមួយៗ
  3. ប្រសិនបើសំណួរប្រភេទត្រូវបន្ថែមតម្លៃបន្ទាប់មកធ្វើបច្ចុប្បន្នភាពតម្លៃនៅទីតាំងខាងឆ្វេង ១ ដោយបន្ថែមតម្លៃ k និងនៅទីតាំងខាងស្តាំដកតម្លៃ k ។
  4. ប្រសិនបើប្រភេទសំណួរត្រូវដកតម្លៃបន្ទាប់មកធ្វើបច្ចុប្បន្នភាពតម្លៃនៅទីតាំងខាងឆ្វេង ១ ដោយដកតម្លៃ k និងនៅទីតាំងខាងស្តាំបន្ថែមតម្លៃ k ។
  5. ឆ្លងកាត់អារេហើយបន្ថែមតម្លៃពីមុននីមួយៗទៅតម្លៃបច្ចុប្បន្ននៃអារេ។
  6. បោះពុម្ពអារេចុងក្រោយ។

ការពន្យល់

យើងត្រូវបានផ្តល់អារេមួយដំបូងតម្លៃទាំងអស់នៅក្នុងអារេគឺ ០ ។ យើងក៏ត្រូវបានផ្តល់ជូនជាមួយផងដែរ q ចំនួននៃសំណួរ, សំណួរនឹងមានពីរប្រភេទ, សំណួរនីមួយៗមាន, ប្រភេទរបស់វា, ជួរ, និងចំនួន k ។ ប្រសិនបើប្រភេទនៃសំណួរគឺ ០ យើងនឹងបន្ថែមតម្លៃ k ទៅចំនួនគត់ទាំងអស់ដែលស្ថិតនៅក្នុងជួរ។ ប្រសិនបើយើងត្រូវបានផ្តល់ប្រភេទនៃសំណួរដែលជា ១ យើងនឹងដកតម្លៃ k ពីចំនួនគត់ទាំងអស់នៅក្នុងជួរ។ បន្ទាប់ពីប្រតិបត្តិសំណួរទាំងអស់យើងនឹងបោះពុម្ពអារេលទ្ធផលនោះ។

សម្រាប់អនុវត្តប្រតិបត្តិការទាំងនេះ។ ដំបូងយើងត្រូវពិនិត្យមើលថាតើប្រភេទសំណួរអ្វីដែលត្រូវបានផ្តល់ឱ្យយើង។ ប្រសិនបើសំណួរមានប្រភេទទីមួយបន្ទាប់មកយើងបន្ថែមតម្លៃ k ទៅចំណុចចាប់ផ្តើមនៃជួរក្នុងជួរអារេ។ ដូចគ្នានេះផងដែរដកតម្លៃ k ពីចំណុចបញ្ចប់នៃជួរនៃអារេ។

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

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

លេខកូដ

កូដ C ++ ដើម្បីបោះពុម្ពអារេដែលបានកែប្រែបន្ទាប់ពីប្រតិបត្តិពាក្យបញ្ជាបន្ថែមនិងដក

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

using namespace std;

void solveQuery(int arr[], int n, int T, int left, int right, int k)
{
    if (T == 0)
    {
        arr[left -1] += k;
        arr[right] += -k;
    }
    else
    {
        arr[left -1] += -k;
        arr[right] += k;
    }
    return;
}

void build(int arr[], int n)
{
    for (int i = 1; i < n; ++i)
        arr[i] += arr[i-1];

    return;
}

int main()
{
    int n = 5;
    int arr[n+1];

    memset(arr, 0, sizeof(arr));


    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 2, 4, 1);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 1, 3, 5, 2);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 1, 4, 3);

    build(arr, n);

    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}
3 4 2 2 -2

កូដចាវ៉ាដើម្បីបោះពុម្ពអារេដែលបានកែប្រែបន្ទាប់ពីប្រតិបត្តិពាក្យបញ្ជាបន្ថែមនិងដក

import java.util.Arrays;

class AdditionSubtractionQuery
{
    static void solveQuery(int arr[], int n, int T, int left, int right, int k)
    {
        if (T == 0)
        {
            arr[left -1] += k;
            arr[right] += -k;
        }
        else
        {
            arr[left -1] += -k;
            arr[right] += k;
        }
        return;
    }
    
    static void build(int arr[], int n)
    {
        for (int i = 1; i < n; ++i)
            arr[i] += arr[i-1];
    }
    
    public static void main(String arg[])
    {
        int n = 5;
        int arr[] = new int[n+1];
        Arrays.fill(arr, 0);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 2, 4, 1);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 1, 3, 5, 2);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 1, 4, 3);

        build(arr, n);

        for (int i = 0; i < n; ++i)
            System.out.print(arr[i]+" ");
    }
}
3 4 2 2 -2

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

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

O (q + n) ដែលជាកន្លែងដែល "Q" គឺជាចំនួនសំណួរនិង “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ពីព្រោះដំបូងយើងធ្វើសំណួរ Q ដែលចំណាយពេល O (1) ហើយបន្ទាប់មកបង្កើតអារេទាមទារពេលវេលា O (N) ។

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

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ចាប់តាំងពីយើងបានបង្កើតអារេមួយដើម្បីអនុវត្តប្រតិបត្តិការ។ ភាពស្មុគស្មាញនៃលំហគឺលីនេអ៊ែរ។