백준 18436번 수열과 쿼리 37 문제풀이(C++)

백준 18436번 수열과 쿼리 37

아이디어

1 i x: Ai를 x로 바꾼다.

2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다.

3 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 홀수의 개수를 출력한다.

홀수/ 짝수 개수 출력 => 입력된 수를 홀수인지 짝수인지 판별 후 펜윅트리에 삽입

※ 값을 바꿀 때, 이전의 수가 홀수였는지 짝수였는지 판별

문제해결

#include<bits/stdc++.h>
using namespace std;
#define MAX 100'000 + 10
int odd[MAX], even[MAX];
int n, m;
void oddInit(int idx, int diff) {
    while (idx <= n + 1) {
        odd[idx] += diff;
        idx += (idx & -idx);
    }
}
void evenInit(int idx, int diff) {
    while (idx <= n + 1) {
        even[idx] += diff;
        idx += (idx & -idx);
    }
}
int oddQuery(int idx) {
    int sum = 0;
    while (idx) {
        sum += odd[idx];
        idx -= (idx & -idx);
    }
    return sum;
}
int evenQuery(int idx) {
    int sum = 0;
    while (idx) {
        sum += even[idx];
        idx -= (idx & -idx);
    }
    return sum;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int num; cin >> num;
        if (num & 1)
            oddInit(i, 1);
        else
            evenInit(i, 1);
    }
    cin >> m;
    while (m--) {
        int i, j, x; cin >> i >> j >> x;
        if (i == 1) {
            int odd = oddQuery(j) - oddQuery(j - 1);
            int even = evenQuery(j) - evenQuery(j - 1);
            if (x & 1) {
                if (even) {
                    evenInit(j, -1);
                    oddInit(j, 1);
                }
            }
            else {
                if (odd) {
                    oddInit(j, -1);
                    evenInit(j, 1);
                }
            }
        }
        else if (i == 2)
            cout << evenQuery(x) - evenQuery(j - 1) << '\n';
        else if (i == 3)
            cout << oddQuery(x) - oddQuery(j - 1) << '\n';
    }
    return 0;
}