סאַכאַקל פון אפילו נומערן נאָך פֿראגן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין טאקע
מענגע

פּראָבלעם סטאַטעמענט

אין דעם פּראָבלעם, מיר באַקומען אַן מענגע פון ינטאַדזשער און מענגע פון ​​ערייז קוויריז. פֿאַר די יטה אָנפֿרעג, מיר וועלן האָבן צוויי פּאַראַמעטערס, ינדעקס און val. נאָך יעדער אָנפֿרעג, מיר לייגן Val צו מענגע [אינדעקס]. מיר דאַרפֿן צו געפֿינען די סומע פון ​​אַלע אפילו ינטאַדזשערז אין די מענגע נאָך יעדער אָנפֿרעג, און ווייַזן עס ווי אַ וועקטאָר פון ינטאַדזשערז.

בייַשפּיל

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

צוגאַנג

ימפּלאַמענטיישאַן פון די סומע פון ​​אפילו נומערן נאָך פֿראגן

איין יקערדיק צוגאַנג וואָלט זיין:

דערהייַנטיקן די קאָראַספּאַנדינג עלעמענט פֿאַר יעדער אָנפֿרעג און דורכפאָר דורך די גאנצע מענגע צו געפֿינען די סומע פון ​​אַלע אפילו נומערן. אָבער, דעם צוגאַנג וואָלט נעמען אָ (ען) צייט פֿאַר יעדער אָנפֿרעג לידינג צו אָ (ען * ק) קוילעלדיק צייט.

מיר קענען טאָן בעסער דורך מיינטיינינג אַ פאַר סאַכאַקל וואָס איז די סומע פון ​​אַלע אפילו נומערן אין די מענגע. פֿאַר יעדער אָנפֿרעג, מיר קענען קאָנטראָלירן צי דער עלעמענט ביי זיין אינדעקס קאַנטריביוטיד צו די אפילו סאַכאַקל פריער קאַלקיאַלייטיד (דורך קאָנטראָלירונג אויב א [אינדעקס]% 2 == 0). אויב יאָ, מיר אַראָפּרעכענען עס פֿון די פליסנדיק סומע און דערהייַנטיקן א [אינדעקס] ווי א [אינדעקס] + וואַל. נאָך דעם, מיר דאַרפֿן צו קאָנטראָלירן ווידער אויב A [אינדעקס] איז גלייך. אויב יאָ, מיר לייגן עס צו אפילו_סומ. דאָס וועט זיין דער ענטפער פֿאַר דער אָנפֿרעג, ווייַל אַלע אנדערע אפילו עלעמענטן בלייבן אַנאַפעקטיד. דעריבער מיר ענטפֿערן יעדער אָנפֿרעג אין אָ (1) צייט.

C ++ פּראָגראַם

#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;
}

Java פּראָגראַם

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 + Q), ווו, N = גרייס פון דער געגעבן מענגע. ק = נומער פון קוויריז. מיר פאַרברענגען O (N) צייט צו געפֿינען די אפילו סאַכאַקל און אָ (ק) צייט צו ענטפֿערן יעדער אָנפֿרעג.

ספעיס קאַמפּלעקסיטי 

אָ (1), ווי מיר נוצן קעסיידערדיק זיקאָרן פּלאַץ.