ಪ್ರಶ್ನೆಗಳ ನಂತರ ಸಮ ಸಂಖ್ಯೆಗಳ ಮೊತ್ತ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ವಾಸ್ತವವಾಗಿ
ಅರೇ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಒಂದು ನೀಡಲಾಗಿದೆ ಸರಣಿ ಸರಣಿಗಳ ಪೂರ್ಣಾಂಕ ಮತ್ತು ರಚನೆಯ ಪ್ರಶ್ನೆಗಳು. ಫಾರ್ ದೆವ್ವದ ಕೂಸು ಪ್ರಶ್ನೆ, ನಾವು ಎರಡು ನಿಯತಾಂಕಗಳನ್ನು ಹೊಂದಿದ್ದೇವೆ, ಸೂಚ್ಯಂಕ ಮತ್ತು ವಾಲ್. ಪ್ರತಿ ಪ್ರಶ್ನೆಯ ನಂತರ, ನಾವು ಸೇರಿಸುತ್ತೇವೆ ಗಂ [ಸೂಚ್ಯಂಕ] ರಚಿಸಲು. ನಾವು ಎಲ್ಲರ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು ಸಹ ಪ್ರತಿ ಪ್ರಶ್ನೆಯ ನಂತರ ರಚನೆಯಲ್ಲಿನ ಪೂರ್ಣಾಂಕಗಳು ಮತ್ತು ಅದನ್ನು ಪೂರ್ಣಾಂಕಗಳ ವೆಕ್ಟರ್ ಆಗಿ ಹಿಂತಿರುಗಿಸಿ.

ಉದಾಹರಣೆ

A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
8 6 2 4
A = [1,2,3,4], queries = [[2,0],[-2,2],[6,0],[4,2]]
6 6 6 6

ಅಪ್ರೋಚ್

ಪ್ರಶ್ನೆಗಳ ನಂತರ ಸಮ ಸಂಖ್ಯೆಗಳ ಮೊತ್ತದ ಅನುಷ್ಠಾನ

ಒಂದು ಮೂಲ ವಿಧಾನ ಹೀಗಿರುತ್ತದೆ:

ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ, ಅನುಗುಣವಾದ ಅಂಶವನ್ನು ನವೀಕರಿಸಿ, ತದನಂತರ ಎಲ್ಲಾ ಸಮ ಸಂಖ್ಯೆಗಳ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಇಡೀ ರಚನೆಯ ಮೂಲಕ ಹಾದುಹೋಗಿರಿ. ಆದರೆ, ಈ ವಿಧಾನವು ಒಟ್ಟಾರೆ ಪ್ರಶ್ನೆಗೆ O (N * Q) ಗೆ ಕಾರಣವಾಗುವ ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ O (N) ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ.

ಎ ಅನ್ನು ನಿರ್ವಹಿಸುವ ಮೂಲಕ ನಾವು ಉತ್ತಮವಾಗಿ ಮಾಡಬಹುದು ಪೂರ್ವ ಮೊತ್ತ ಇದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಎಲ್ಲಾ ಸಮ ಸಂಖ್ಯೆಗಳ ಮೊತ್ತವಾಗಿದೆ. ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ, ಅದರ ಸೂಚ್ಯಂಕದಲ್ಲಿನ ಅಂಶವು ಇದಕ್ಕೆ ಕೊಡುಗೆ ನೀಡುತ್ತಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಬಹುದು ಸಹ ಮೊತ್ತ ಮೊದಲೇ ಲೆಕ್ಕಹಾಕಲಾಗಿದೆ (ಎ [ಸೂಚ್ಯಂಕ]% 2 == 0 ಎಂದು ಪರಿಶೀಲಿಸುವ ಮೂಲಕ). ಹೌದು, ನಾವು ಅದನ್ನು ಚಾಲನೆಯಲ್ಲಿರುವ ಮೊತ್ತದಿಂದ ಕಳೆಯುತ್ತೇವೆ ಮತ್ತು ಎ [ಸೂಚ್ಯಂಕ] ವನ್ನು ಎ [ಸೂಚ್ಯಂಕ] + ಮೌಲ್ಯವಾಗಿ ನವೀಕರಿಸುತ್ತೇವೆ. ಅದರ ನಂತರ, ಎ [ಸೂಚ್ಯಂಕ] ಸಮವಾಗಿದೆಯೇ ಎಂದು ನಾವು ಮತ್ತೆ ಪರಿಶೀಲಿಸಬೇಕಾಗಿದೆ. ಹೌದು, ನಾವು ಅದನ್ನು ಸೇರಿಸುತ್ತೇವೆ even_sum. ಎಲ್ಲಾ ಇತರ ಅಂಶಗಳು ಸಹ ಪರಿಣಾಮ ಬೀರದ ಕಾರಣ ಇದು ಆ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ನಾವು ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ ಒ (1) ಸಮಯದಲ್ಲಿ ಉತ್ತರಿಸುತ್ತೇವೆ.

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <bits/stdc++.h>

using namespace std;

vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
    int evenSum = 0;

    for(int &x : A) {
        if(x % 2 == 0) {
            evenSum += x;
        }
    }

    int n = queries.size() , val , idx;
    vector <int> ans(n);
    for(int i = 0 ; i < n ; i++) {
        val = queries[i][0] , idx = queries[i][1];
        if(A[idx] % 2 == 0) evenSum -= A[idx];
        A[idx] += val;
        if(A[idx] % 2 == 0) evenSum += A[idx];
        ans[i] = evenSum;
    }

    return ans;
}

int main() {
    vector <int> A = {1 , 2 , 3 , 4};
    vector < vector <int> > queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}};
    vector <int> ans = sumEvenAfterQueries(A , queries);
    for(int &x : ans)
        cout << x << " ";
    cout << endl;
    return 0;
}

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

class sum_even_after_queries {
    public static void main(String args[]) {
        int[] A = {1 , 2 , 3 , 4};
        int[][] queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}};
        int[] ans = sumEvenAfterQueries(A , queries);
        for(int x : ans)
            System.out.print(x + " ");
        System.out.println();
    }

    public static int[] sumEvenAfterQueries(int[] A, int[][] queries) {
        int evenSum = 0;

        for(int x : A) {
            if(x % 2 == 0) {
                evenSum += x;
            }
        }
        int n = queries.length , val , idx;
        int[] ans = new int[n];
        for(int i = 0 ; i < n ; i++) {
            val = queries[i][0];
            idx = queries[i][1];

            if(A[idx] % 2 == 0) evenSum -= A[idx];
            A[idx] += val;
            if(A[idx] % 2 == 0) evenSum += A[idx];
            ans[i] = evenSum;
        }

        return ans;
    }
}
8 6 2 4

ಪ್ರಶ್ನೆಗಳ ನಂತರ ಸಮ ಸಂಖ್ಯೆಗಳ ಸಂಕೀರ್ಣತೆಯ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಎನ್ + ಕ್ಯೂ), ಅಲ್ಲಿ, ಕೊಟ್ಟಿರುವ ರಚನೆಯ N = ಗಾತ್ರ. ಪ್ರಶ್ನೆ = ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆ. ಕಂಡುಹಿಡಿಯಲು ನಾವು ಒ (ಎನ್) ಸಮಯವನ್ನು ಕಳೆಯುತ್ತೇವೆ ಸಹ ಮೊತ್ತ ಮತ್ತು ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸಲು O (Q) ಸಮಯ.

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

ಒ (1), ನಾವು ಸ್ಥಿರ ಮೆಮೊರಿ ಸ್ಥಳವನ್ನು ಬಳಸುತ್ತಿದ್ದಂತೆ.