थप र घटाउको आदेशहरू कार्यान्वयन पछि परिमार्जित एरे प्रिन्ट गर्नुहोस्


कठिनाई तह मध्यम
बारम्बार सोधिन्छ बाइटडेन्स सिस्को citrix फ्रीचार्ज हैकरर्यांक नागररो ओपेरा टेराडाटा
एरे

तपाईंलाई आकार एनको एर्रे दिइन्छ, सुरुमा एर्रेमा सबै मान ०, र क्वेरीहरू हुन्छन्। प्रत्येक क्वेरीले चार मानहरू, क्वेरीको प्रकार T, दायराको बायाँ पोइन्ट, दायराको दायाँ पोइन्ट र नम्बर k समावेश गर्दछ, तपाईंले निम्न कार्यहरू गर्नुपर्दछ।

यदि T = 0, दिइएको k दायरा भित्र सुरूवात (सुरू, अन्त) मा सबै पूर्णांकमा मान k थप गर्नुहोस्,

यदि T = 1, दिईएको दायरा भित्रै सबै पूर्णाgers्कबाट मान 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

स्पष्टीकरण

(०, २,,, १) दायरा भित्रका सबै पूर्णाgers्कहरू १ थप्नुहोस् किनकि यो टाइप ० क्वेरी हो।

(१,,,,, २) दायरा भित्रका सबै पूर्णांकबाट २ घटाउनुहोस् किनकि यो टाइप १ क्वेरी हो।

(०, २,,, १) दायरा भित्रका सबै पूर्णाgers्कहरू १ थप्नुहोस् किनकि यो टाइप ० क्वेरी हो।

थप र घटाउको आदेशहरू कार्यान्वयन पछि परिमार्जित एरे प्रिन्ट गर्नुहोस्

 

धेरै प्रश्नहरू पछि संशोधित एरे प्रिन्ट गर्न एल्गोरिथ्म

  1. सुरु गर्नुहोस् array २०..0 को साथ।
  2. प्रत्येक क्वेरीको लागि,
  3. यदि प्रकार क्वेरी मान थप्न को लागी, तब मान k थपेर दायाँ स्थिति मा बायाँ -१ स्थिति मा मान अपडेट गर्नुहोस् र मान k लाई घटाउनुहोस्।
  4. यदि प्रकार क्वेरी मानलाई घटाउन हो भने, त्यसपछि मान 'K' घटाएर बायाँ १ स्थितिमा मान अपडेट गर्नुहोस् र दायाँ स्थितिमा मान 'के' थप्नुहोस्।
  5. एर्रे पार गर्नुहोस् र एर्रेको हालको मानमा प्रत्येक अघिल्लो मान थप गर्नुहोस्।
  6. अन्तिम एरे प्रिन्ट गर्नुहोस्।

स्पष्टीकरण

हामीलाई एर्रे दिइन्छ, सुरुमा एरेमा सबै मान ० हुन्छ। हामी पनि a बाट प्रदान गरीन्छौं q प्रश्नहरूको संख्या, क्वेरी दुई प्रकारको हुनेछ, प्रत्येक क्वेरी समावेश गर्दछ, यसको प्रकार, दायरा, र एक संख्या k। यदि क्वेरीको प्रकार ० छ भने, हामी मान k लाई सबै इन्टेजरहरू जोड्दछौं जुन दायरा भित्र आउँछ। यदि हामीलाई क्वेरीको प्रकार १ को रूपमा दिइन्छ भने, हामी दायरा भित्र सबै ईन्टिजरबाट मान kलाई घटाउनेछौं। सबै प्रश्नहरू कार्यान्वयन पछि, हामी त्यो परिणाम एर्रे प्रिन्ट गर्दैछौं।

यी कार्यहरू प्रदर्शन गर्नका लागि। पहिले हामीले जाँच गर्नु पर्छ कि हामीलाई कस्तो प्रकारको क्वेरी दिइयो। यदि क्वेरी पहिलो प्रकारको हो भने हामी एरेमा दायराको सुरूवात बिन्दुमा मान k थप गर्दछौं। साथै, मान श्रेणीलाई एरेको दायराको अन्त्य बिन्दुबाट घटाउनुहोस्।

हामी अघिल्लो उल्लिखित प्रविधिको विपरित कार्य गर्ने छौं। यदि हामीलाई टाइप १ क्वेरी प्रयोग गर्न दिइन्छ जसमा हामीले दायरा भित्रै पूर्णा ar्क एरेको मानको सबै घटाउनु पर्छ। त्यसो भए हामी एउटा मानको सुरूवात दायरा बाट मान 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) जहाँ "क्यू" क्वेरीहरूको संख्या हो, र "N" एर्रेमा एलिमेन्ट्सको संख्या हो। किनकि पहिले हामी Q प्रश्नहरू गर्छौं जसले O (१) लिन्छ र त्यसपछि एर्रे बनाउन O (N) समय आवश्यक हुन्छ।

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। हामीले अपरेसनमा कार्यहरू गर्नको लागि एर्रे सिर्जना गरेका छौं। ठाउँ जटिलता रैखिक छ।