문제

백준 18436

설명

길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• i x: Ai를 x로 바꾼다.
• l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다.
• l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 홀수의 개수를 출력한다.

수열의 인덱스는 1부터 시작한다.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ i ≤ N, 1 ≤ l ≤ r ≤ N, 1 ≤ x ≤ 109)

출력

2, 3번 쿼리의 정답을 한 줄에 하나씩 출력한다.

풀이 방법

수열의 값을 바꾸는 방법은 어렵지 않다 수열 A 의 인덱스 값에 새로운 값을 대입해주기만 하면 된다.

그렇다면 이제 특정 구간안에 있는 짝수와 홀수의 개수를 구하기만 하면된다.

가장 쉽게 생각 할 수 있는 방법은 구간을 전부 탐색하면서 짝수와 홀수의 개수를 구하는 것이다.

하지만 이런 방법으로 접근하면 시간복잡도가 O(N^2) 이므로 해당 문제를 제한 시간안에 풀지 못한다.

결국 이 문제를 풀려면 O(N * log(N)) 인 알고리즘을 떠올려야 한다.

세그먼트 트리

세그먼트 트리를 사용해 이 문제를 O(N * log(N)) 에 풀 수 있다.

먼저 세그먼트 트리의 노드에 각 구간의 짝수개수, 홀수 개수 정보를 저장한다.

typedef struct{
    int odd;
    int even;
} Node;

이후 트리의 정보를 초기화 해준다.

Node make_tree(int i, int s, int e)
{
    if (s == e) return tree[i] = {arr[s] % 2, !(arr[s] % 2)};
    int m = (s + e) / 2;
    Node left_tree = make_tree(i * 2, s, m);
    Node right_tree = make_tree(i * 2 + 1, m + 1, e);
    tree[i] = {left_tree.odd + right_tree.odd, left_tree.even +  right_tree.even};
    return tree[i];
}

A[i] 의 값의 변경이 있을 때 마다 트리의 정보를 업데이트 해줘야한다. 해당 함수를 구현한다

void update(int i, int s, int e, int target_index, bool isodd)
{

    if (target_index < s || target_index > e)
        return;

    if (s == e) {
        tree[i] = {isodd, !isodd};
        return;
    }

    int m = (s + e) / 2;
    tree[i] = {tree[i].odd + isodd - !isodd, tree[i].even + !isodd - isodd};
    update(i * 2, s, m, target_index, isodd);
    update(i * 2 + 1, m + 1, e, target_index, isodd);
    return;
}

구간의 정보를 활용해 짝수와 홀수의 개수를 찾는 함수를 구현한다.

Node find(int i, int l, int r, int s, int e)
{
    if (s > r || e < l)
        return {0, 0};

    if (s >= l && e <= r)
    {
        return {tree[i].odd, tree[i].even};
    }
    int m = (s + e) / 2;
    Node left_find = find(i * 2, l, r, s, m);
    Node right_find = find(i * 2 + 1, l, r, m + 1, e);

    return {left_find.odd + right_find.odd, left_find.even + right_find.even};
}

쿼리문을 작성해준다.

void query(int num)
{
    int l, r, x, i;
    if (num == 1)
    {
        cin >> i >> x;
        if (arr[i] % 2 != x % 2)
        {
            update(1, 1, N, i, x % 2);
            arr[i] = x;
        }
        return;
    }

    cin >> l >> r;
    Node node = find(1, l, r, 1, N);
    cout << (num == 2 ? node.even : node.odd) << "\n";
}

🔔 마치며..