ಸೇರ್ಪಡೆ ಮತ್ತು ವ್ಯವಕಲನ ಆಜ್ಞೆಗಳನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಿದ ನಂತರ ಮಾರ್ಪಡಿಸಿದ ರಚನೆಯನ್ನು ಮುದ್ರಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಬೈಟ್ ಡೇನ್ಸ್ ಸಿಸ್ಕೋ ಸಿಟ್ರಿಕ್ಸ್ ಫ್ರೀಚಾರ್ಜ್ ಹ್ಯಾಕರ್ರ್ಯಾಂಕ್ ನಾಗರೋ ಒಪೆರಾ ಟೆರಾಡಾಟಾ
ಅರೇ

ನಿಮಗೆ ಗಾತ್ರ n ನ ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗಿದೆ, ಆರಂಭದಲ್ಲಿ ರಚನೆಯ ಎಲ್ಲಾ ಮೌಲ್ಯಗಳು 0 ಆಗಿರುತ್ತದೆ ಮತ್ತು ಪ್ರಶ್ನೆಗಳು. ಪ್ರತಿಯೊಂದು ಪ್ರಶ್ನೆಯು ನಾಲ್ಕು ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಪ್ರಶ್ನೆಯ ಪ್ರಕಾರ, ಶ್ರೇಣಿಯ ಎಡ ಬಿಂದು, ಶ್ರೇಣಿಯ ಬಲ ಬಿಂದು ಮತ್ತು ಒಂದು ಸಂಖ್ಯೆ ಕೆ, ನೀವು ಈ ಕೆಳಗಿನ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ನಿರ್ವಹಿಸಬೇಕು.

ಟಿ = 0 ಆಗಿದ್ದರೆ, ಕೊಟ್ಟಿರುವ ಶ್ರೇಣಿಯಲ್ಲಿನ ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯಲ್ಲಿನ (ಪ್ರಾರಂಭ, ಅಂತ್ಯ) ಎಲ್ಲ ಪೂರ್ಣಾಂಕಗಳಿಗೆ ಕೆ ಮೌಲ್ಯವನ್ನು ಸೇರಿಸಿ,

ಟಿ = 1 ಆಗಿದ್ದರೆ, ಕೊಟ್ಟಿರುವ ಶ್ರೇಣಿಯಲ್ಲಿನ ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯೊಳಗೆ (ಪ್ರಾರಂಭ, ಅಂತ್ಯ) ಎಲ್ಲಾ ಪೂರ್ಣಾಂಕಗಳಿಂದ ಕೆ ಮೌಲ್ಯವನ್ನು ಕಳೆಯಿರಿ,

ಉದಾಹರಣೆ

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. ಟೈಪ್ ಪ್ರಶ್ನೆಯು ಮೌಲ್ಯಗಳನ್ನು ಕಳೆಯುವುದಾದರೆ, ಕೆ ಮೌಲ್ಯವನ್ನು ಕಳೆಯುವ ಮೂಲಕ ಎಡ -1 ಸ್ಥಾನದಲ್ಲಿ ಮೌಲ್ಯವನ್ನು ನವೀಕರಿಸಿ ಮತ್ತು ಸರಿಯಾದ ಸ್ಥಾನದಲ್ಲಿ ಕೆ ಮೌಲ್ಯವನ್ನು ಸೇರಿಸಿ.
  5. ರಚನೆಯ ಮೂಲಕ ಹಾದುಹೋಗಿರಿ ಮತ್ತು ಪ್ರತಿ ಹಿಂದಿನ ಮೌಲ್ಯವನ್ನು ರಚನೆಯ ಪ್ರಸ್ತುತ ಮೌಲ್ಯಕ್ಕೆ ಸೇರಿಸಿ.
  6. ಅಂತಿಮ ಶ್ರೇಣಿಯನ್ನು ಮುದ್ರಿಸಿ.

ವಿವರಣೆ

ನಮಗೆ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗಿದೆ, ಆರಂಭದಲ್ಲಿ, ರಚನೆಯ ಎಲ್ಲಾ ಮೌಲ್ಯಗಳು 0. ನಮಗೆ ಸಹ ಒದಗಿಸಲಾಗಿದೆ a q ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆ, ಪ್ರಶ್ನೆಯು ಎರಡು ಪ್ರಕಾರಗಳಾಗಿರುತ್ತದೆ, ಪ್ರತಿ ಪ್ರಶ್ನೆಯು ಅದರ ಪ್ರಕಾರ, ಶ್ರೇಣಿ ಮತ್ತು ಒಂದು ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಪ್ರಶ್ನೆಯ ಪ್ರಕಾರವು 0 ಆಗಿದ್ದರೆ, ನಾವು ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಬರುವ ಎಲ್ಲಾ ಪೂರ್ಣಾಂಕಗಳಿಗೆ k ಮೌಲ್ಯವನ್ನು ಸೇರಿಸುತ್ತೇವೆ. ನಮಗೆ ಪ್ರಶ್ನೆಯ ಪ್ರಕಾರವನ್ನು 1 ಎಂದು ನೀಡಿದರೆ, ನಾವು ಎಲ್ಲಾ ಪೂರ್ಣಾಂಕಗಳಿಂದ k ಮೌಲ್ಯವನ್ನು ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಕಳೆಯುತ್ತೇವೆ. ಎಲ್ಲಾ ಪ್ರಶ್ನೆಗಳನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಿದ ನಂತರ, ನಾವು ಆ ಫಲಿತಾಂಶದ ಶ್ರೇಣಿಯನ್ನು ಮುದ್ರಿಸುತ್ತೇವೆ.

ಈ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ನಿರ್ವಹಿಸಲು. ಮೊದಲು ನಮಗೆ ಯಾವ ರೀತಿಯ ಪ್ರಶ್ನೆಯನ್ನು ನೀಡಲಾಗಿದೆ ಎಂಬುದನ್ನು ಪರಿಶೀಲಿಸಬೇಕು. ಪ್ರಶ್ನೆಯು ಮೊದಲ ಪ್ರಕಾರದಲ್ಲಿದ್ದರೆ, ನಾವು ಶ್ರೇಣಿಯಲ್ಲಿನ ಶ್ರೇಣಿಯ ಪ್ರಾರಂಭದ ಹಂತಕ್ಕೆ k ಮೌಲ್ಯವನ್ನು ಸೇರಿಸುತ್ತೇವೆ. ಅಲ್ಲದೆ, ರಚನೆಯ ಶ್ರೇಣಿಯ ಅಂತ್ಯದ ಬಿಂದುವಿನಿಂದ k ಮೌಲ್ಯವನ್ನು ಕಳೆಯಿರಿ.

ನಾವು ಹಿಂದೆ ಹೇಳಿದ ತಂತ್ರಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ ಮಾಡುತ್ತೇವೆ. ಟೈಪ್ 1 ಪ್ರಶ್ನೆಯನ್ನು ಬಳಸಲು ನಮಗೆ ನೀಡಿದರೆ, ಇದರಲ್ಲಿ ನಾವು ಪೂರ್ಣಾಂಕ ರಚನೆಯ ಎಲ್ಲಾ ಮೌಲ್ಯಗಳನ್ನು ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಕಳೆಯಬೇಕಾಗುತ್ತದೆ. ನಂತರ ನಾವು ಒಂದು ಶ್ರೇಣಿಯ ಆರಂಭಿಕ ಶ್ರೇಣಿಯ ಮೌಲ್ಯದಿಂದ k ಮೌಲ್ಯವನ್ನು ಕಳೆಯುತ್ತೇವೆ. ಅದರ ನಂತರ, ಶ್ರೇಣಿಯ ಎಂಡ್‌ಪಾಯಿಂಟ್ ಸೂಚ್ಯಂಕದಲ್ಲಿ ಕೆ ಮೌಲ್ಯವನ್ನು ಸೇರಿಸಿ.

ನೀಡಿರುವ ಪ್ರತಿಯೊಂದು ಪ್ರಶ್ನೆಗಳಿಗೆ. ನಾವು ಪ್ರಸ್ತಾಪಿಸಿದ ತಂತ್ರವನ್ನು ನಿರ್ವಹಿಸಬೇಕು. ನಂತರ ನಾವು ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನಿರ್ಮಿಸುತ್ತೇವೆ, ಇದರಲ್ಲಿ ನಾವು ಹಿಂದಿನ ಮೌಲ್ಯವನ್ನು ರಚನೆಯ ಪ್ರಸ್ತುತ ಮೌಲ್ಯಕ್ಕೆ ಸೇರಿಸುತ್ತೇವೆ. ಮತ್ತು ಮೊತ್ತವನ್ನು ಪ್ರಸ್ತುತ ಮೌಲ್ಯಕ್ಕೆ ಸಂಗ್ರಹಿಸಿ. ಅಥವಾ ನಾವು ರಚನೆಯ ಪ್ರಸ್ತುತ ಮೌಲ್ಯವನ್ನು ನವೀಕರಿಸುತ್ತೇವೆ ಎಂದು ಹೇಳಬಹುದು. ರಚನೆಯನ್ನು ನಿರ್ಮಿಸಿದ ನಂತರ, ನಾವು ರಚನೆಯನ್ನು ಮುದ್ರಿಸುತ್ತೇವೆ. ಅದು ಮಾರ್ಪಡಿಸಿದ ರಚನೆಯ ಅಪೇಕ್ಷಿತ ಫಲಿತಾಂಶವಾಗಿರುತ್ತದೆ.

ಕೋಡ್

ಸೇರ್ಪಡೆ ಮತ್ತು ವ್ಯವಕಲನ ಆಜ್ಞೆಗಳನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಿದ ನಂತರ ಮಾರ್ಪಡಿಸಿದ ಶ್ರೇಣಿಯನ್ನು ಮುದ್ರಿಸಲು ಸಿ ++ ಕೋಡ್

#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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (q + n) ಅಲ್ಲಿ "ಪ್ರಶ್ನೆ" ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆ, ಮತ್ತು “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಏಕೆಂದರೆ ಮೊದಲು ನಾವು O (1) ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುವ Q ಪ್ರಶ್ನೆಗಳನ್ನು ನಿರ್ವಹಿಸುತ್ತೇವೆ ಮತ್ತು ನಂತರ ರಚನೆಯನ್ನು ನಿರ್ಮಿಸಲು O (N) ಸಮಯ ಬೇಕಾಗುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ನಿರ್ವಹಿಸಲು ನಾವು ಒಂದು ಶ್ರೇಣಿಯನ್ನು ರಚಿಸಿದ್ದರಿಂದ. ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ.