수열과 쿼리 37

문제 분석 및 풀이

설계 분석

• 자주 변경되는 데이터에 맞는 자료구조가 세그먼트 트리임을 알면 쉽게 접근할 수 있는 문제
• 여기서는 짝수의 개수 혹은 홀수의 개수를 세그먼트 트리로 관리하면 $O(logN)$으로 구할 수 있음.

• $O(logM)$

풀이

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 100001;
// 홀수만 저장하는 세그먼트 트리
int oddSegTree[4 * MAX];
// 실제 수열에 홀수가 있는지 짝수가 있는지 저장하는 배열
// 0이면 짝수 1이면 홀수
int seqArr[MAX];
int N, M;

void UpdateTree(int node, int left, int right, int idx, int diff)
{
    if (left > idx || idx > right) return;
    oddSegTree[node] += diff;
    if (left == right) return;

    int mid = (left + right) / 2;
    UpdateTree(node * 2, left, mid, idx, diff);
    UpdateTree(node * 2 + 1, mid+1, right, idx, diff);
}

// [targetLeft, targetRight] 범위의 합을 구하는 함수
int query(int node, int left, int right, int targetLeft, int targetRight)
{
    if (targetLeft <= left && right <= targetRight) return oddSegTree[node];
    if (targetLeft > right || left > targetRight) return 0;

    int mid = (left + right) / 2;
    return query(node * 2, left, mid , targetLeft, targetRight)
    + query(node * 2 + 1, mid + 1, right, targetLeft, targetRight);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    for (int i=1; i<=N; i++)
    {
        int inval;
        cin >> inval;
        // 홀수인 경우 트리 갱신
        if (inval % 2 != 0)
        {
            seqArr[i] = 1;
            UpdateTree(1,1,N,i,1); 
        }
    }
    
    cin >> M;

    for (int i=0; i<M; i++)
    {
        int cmd, a, b;
        cin >> cmd;
        if (cmd == 1)
        {
        	// a위치의 값을 b로 바꾼다.
            cin >> a >> b;
            // a위치에 있던값이 짝수이고 바뀔 값이 홀수
            if (seqArr[a] == 0 && b % 2 != 0)
            {
            	// 홀수로 바꾸기
                seqArr[a] = 1;
                // 홀수의 개수 +1
                UpdateTree(1,1,N,a,1); 
            }
			// a위치에 있던값이 홀수이고 바뀔 값이 짝수
            else if (seqArr[a] == 1 && b % 2 == 0)
            {
            	// 짝수로 바꾸기
                seqArr[a] = 0;
                // 홀수의 개수 -1
                UpdateTree(1,1,N,a,-1); 
            }
        }
        else if (cmd == 2)
        {
        	// [a,b]의 짝수 개수 출력
            // 홀수 개수 구해서 빼기
            cin >> a >> b;
            cout << (b-a + 1) - query(1,1,N,a,b) << "\n";
        }
        else if (cmd == 3)
        {
        	// [a,b]의 홀수 개수 출력
            cin >> a >> b;
            cout << query(1,1,N,a,b) << "\n";
        }
    }

    return 0;
}