백준 18436번 수열과 쿼리 37 C++ 세그먼트 트리

리뷰

세그먼트 트리 누적합을 활용하여 푸는 문제

 

문제 풀이

1. n개의 수를 입력 받을 때 홀수일 경우 -1로 짝수일 경우 1로 저장해 준다. (반대로 해도 상관 없다.)
2. 이후 누적합 세그먼트 트리의 build, update, query를 동일하게 작성해 준다.
3. 쿼리를 입력 받고 케이스2라면 짝수의 개수를 케이스3이라면 홀수의 개수를 노출해 줄 것이다.
4. 짝수를 1로 저장했을 경우 (구간의 범위 + 쿼리의 출력값)을 2로 나누어 주면 짝수의 개수를 알 수 있다.
5. 홀수를 -1로 저장했을 경우 (쿼리의 답 - 구간의 범위)의 절댓값을 2로 나누어 주면 홀수의 개수를 알 수 있다.

 

참고 사항

구간의 범위가 4이고 짝수가 4 ~ 0개일때의 출력값

4 4 4
4 3 2
4 2 0
4 1 -2
4 0 -4

4 4 4 일때 짝수의 개수는 4(범위) + 4(쿼리의 출력 값) / 2 = 4개

4 2 0 일때 홀수의 개수는 0(쿼리의 출력 값) - 4(범위)의 절댓값 = abs(-4) = 4 / 2 = 2개

 

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> tree;

void build(vector<int>& lst, int node, int start, int end) {
    if (start == end) tree[node] = lst[start];
    else {
        int mid = (start + end) / 2;
        build(lst, node * 2, start, mid);
        build(lst, node * 2 + 1, mid + 1, end);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

void update(int node, int start, int end, int idx, int val) {
    if (start == end) tree[node] = val;
    else {
        int mid = (start + end) / 2;
        if (start <= idx && idx <= mid) update(node * 2, start, mid, idx, val);
        else update(node * 2 + 1, mid + 1, end, idx, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

int query(int node, int start, int end, int L, int R) {
    if (R < start || end < L) {
        return 0;
    }
    if (L <= start && end <= R) {
        return tree[node];
    }
    int mid = (start + end) / 2;
    int left = query(node * 2, start, mid, L, R);
    int right = query(node * 2 + 1, mid + 1, end, L, R);
    return left + right;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    vector<int> lst(n);
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        if (temp % 2) lst[i] = -1;
        else lst[i] = 1;
    }
    tree.resize(4 * n);
    build(lst, 1, 0, n - 1);
    cin >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1) {
            if (c % 2) c = -1;
            else c = 1;
            update(1, 0, n - 1, b - 1, c);
        }
        else {
            int ans = query(1, 0, n - 1, b - 1, c - 1);
            if (a == 2) cout << (c - b + 1 + ans) / 2 << "\n";
            if (a == 3) cout << abs(ans - (c - b + 1)) / 2 << "\n";
        }
    }
}