Қосу және азайту командаларын орындағаннан кейін өзгертілген массивті басып шығарыңыз


Күрделілік дәрежесі орта
Жиі кіреді ByteDance Cisco Citrix FreeCharge HackerRank Нагарро опера Терадата
Array

Сізге n өлшемді жиым беріледі, бастапқыда жиымдағы барлық мәндер 0 болады, ал сұраулар. Әр сұраныс төрт мәнді, сұраныстың түрін, диапазонның сол нүктесін, диапазонның оң нүктесін және 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

Түсіндіру

(0, 2, 4, 1) диапазондағы барлық бүтін сандарға 1 қосыңыз, себебі ол 0 типті сұраныс болып табылады.

(1, 3, 5, 2) диапазондағы барлық бүтін сандардан 2-ді алып тастаңыз, өйткені бұл 1 типті сұраныс.

(0, 1, 4, 3) диапазондағы барлық бүтін сандарға 3 қосыңыз, себебі ол 0 типті сұраныс болып табылады.

Қосу және азайту командаларын орындағаннан кейін өзгертілген массивті басып шығарыңыз

 

Бірнеше сұраныстан кейін модификацияланған массивті басып шығару алгоритмі

  1. Инициализациясы массив бірге 0.
  2. Әр сұраныс үшін,
  3. Егер типтік сұраныс мәндерді қосу керек болса, онда k-мәнін қосу арқылы сол жақтағы 1 мәнін жаңартып, k мәнін алып тастаңыз.
  4. Егер типтік сұраныс мәндерді алып тастауға арналған болса, онда k мәнін алып тастап, сол жақтағы 1 мәніндегі мәнді жаңартыңыз, ал оң жақта k мәнін қосыңыз.
  5. Массивті айналып өтіп, әрбір алдыңғы мәнді жиымның ағымдағы мәніне қосыңыз.
  6. Соңғы жиымды басып шығарыңыз.

Түсіндіру

Бізге массив беріледі, бастапқыда массивтің барлық мәндері 0-ге тең. Бізге a q сұраулар саны, сұраныс екі түрден тұрады, әр сұрауда оның түрі, ауқымы және k саны болады. Егер сұрау түрі 0-ге тең болса, онда барлық мәндерге k мәнін қосамыз. Егер бізге сұраныстың түрі 1 түрінде берілсе, онда бүтін сандардың арасынан 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

Қосу және азайту командаларын орындағаннан кейін модификацияланған массивті басып шығаруға арналған Java коды

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» - бұл массивтегі элементтер саны. Алдымен O (1) уақытты алатын Q сұрауларын орындаймыз, содан кейін массивті құру O (N) уақытты қажет етеді.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны. Біз операцияларды орындау үшін массив құрдық. Кеңістіктің күрделілігі сызықтық болып табылады.