එකතු කිරීමේ හා අඩු කිරීමේ විධානයන් ක්‍රියාත්මක කිරීමෙන් පසු නවීකරණය කරන ලද අරාව මුද්‍රණය කරන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ByteDance සිස්කෝ Citrix FreeCharge හැකර් රැන්ක් නාගරෝ ඔපෙරා Teradata
අරා

ඔබට n ප්‍රමාණයේ අරාවක් ලබා දී ඇත, මුලදී අරාවෙහි ඇති සියලුම අගයන් 0 වනු ඇත, සහ විමසුම්. සෑම විමසුමකම අගයන් හතරක් අඩංගු වේ, විමසුම් වර්ගය, පරාසයේ වම් ලක්ෂ්‍යය, පරාසයක දකුණු ලක්ෂ්‍යය සහ කේ අංකයක්, ඔබට පහත සඳහන් මෙහෙයුම් සිදු කළ යුතුය.

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 අගය අඩු කරන්නෙමු. සියලුම විමසුම් ක්‍රියාත්මක කිරීමෙන් පසුව, අපි එම ප්‍රති ar ල අරා මුද්‍රණය කරන්නෙමු.

මෙම මෙහෙයුම් සිදු කිරීම සඳහා. පළමුවෙන්ම අපට ලබා දෙන්නේ කුමන ආකාරයේ විමසුමක්ද යන්න පරීක්ෂා කර බැලිය යුතුය. විමසුම පළමු වර්ගයේ නම්, අපි අරාවෙහි පරාසයේ ආරම්භක ස්ථානයට k අගය එකතු කරමු. තවද, අරාව පරාසයේ අවසාන ලක්ෂ්‍යයෙන් k අගය අඩු කරන්න.

කලින් සඳහන් කළ තාක්ෂණයට ප්‍රතිවිරුද්ධ දේ අපි කරන්නෙමු. 1 වන වර්ගයේ විමසුමක් භාවිතා කිරීමට අපට ලබා දී ඇත්නම්, පූර්ණ සංඛ්‍යා අරාවෙහි සියලු අගයන් පරාසය තුළ අඩු කළ යුතුය. එවිට අපි අරාවෙහි ආරම්භක පරාසයේ අගයෙන් k අගය අඩු කරමු. ඊට පසු, පරාසයේ අන්ත ලක්ෂ්‍ය දර්ශකයේ k අගය එකතු කරන්න.

ලබා දී ඇති එක් එක් විමසුම් සඳහා. අප විසින් සඳහන් කළ තාක්ෂණය සිදු කළ යුතුය. එවිට අපි අරාව ගොඩනඟමු, එහිදී අපි පෙර අගය අරාවේ වත්මන් අගයට එකතු කරමු. එම මුදල වත්මන් වටිනාකමට ගබඩා කරන්න. නැතහොත් අපි අරාවෙහි වත්මන් අගය යාවත්කාලීන කරන බව පැවසිය හැකිය. අරාවක් තැනීමෙන් පසු, අපි අරාව මුද්‍රණය කරන්නෙමු. එය නවීකරණය කරන ලද අරාවක අපේක්ෂිත ප්‍රති result ලය වනු ඇත.

කේතය

එකතු කිරීමේ හා අඩු කිරීමේ විධානයන් ක්‍රියාත්මක කිරීමෙන් පසුව නවීකරණය කරන ලද අරාව මුද්‍රණය කිරීම සඳහා 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” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. මෙහෙයුම් සිදු කිරීම සඳහා අපි අරාවක් නිර්මාණය කළ බැවින්. අවකාශයේ සංකීර්ණතාව රේඛීය වේ.