Асуулгын дараах тэгш тоо


Хэцүү байдлын түвшин Easy
Байнга асуудаг Үнэндээ
Array

Асуудлын мэдэгдэл

Энэ асуудалд бидэнд массив массивын бүхэл тоо ба массив асуулга. Учир нь ith асуулга, бид хоёр параметртэй байх болно, индекс болон вал. Асуулт бүрийн дараа бид нэмж оруулав Нэрлэсэн үнэ массив руу [индекс]. Бид бүгдийн нийлбэрийг олох хэрэгтэй тэр ч байтугай асуулга бүрийн дараа массив дахь бүхэл тоонууд, түүнийг бүхэл тоон вектор болгон буцаана.

Жишээ нь

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) цаг хугацаа шаардагдана.

A-г хадгалах замаар бид илүү сайн хийж чадна урьдчилсан дүн Энэ нь массив дахь бүх тэгш тоонуудын нийлбэр юм. Асуулт бүрийн хувьд индекс дэх элемент нь хувь нэмэр оруулсан эсэхийг шалгаж болно тэр ч байтугай нийлбэр өмнө тооцсон (A [индекс]% 2 == 0 эсэхийг шалгаж). Хэрэв тийм бол бид ажиллаж байгаа нийлбэрээс хасаад A [индекс] -ийг A [индекс] + вал гэж шинэчилнэ. Үүний дараа бид А [индекс] тэгш байгаа эсэхийг дахин шалгах хэрэгтэй. Хэрэв тийм бол бид үүнийг нэмнэ тэгш_сум. Бусад бүх элементүүд нөлөөлөлд өртөхгүй хэвээр байгаа тул энэ асуултын хариулт байх болно. Тиймээс бид асуулга бүрт O (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

Асуулгын дараа тэгш тооны нийлбэр дүн шинжилгээ хийх

Цаг хугацааны нарийн төвөгтэй байдал

O (N + Q), хаана, N = өгөгдсөн массивын хэмжээ. Q = асуулгын тоо. Бид олохын тулд O (N) цагийг зарцуулдаг тэр ч байтугай нийлбэр Асуулт бүрт хариулах O (Q) хугацаа.

Сансрын нарийн төвөгтэй байдал 

O (1), бид байнгын санах ойн зайг ашигладаг тул.