C++로 q번의 범위 갱신 연산 후 배열에 남은 서로 다른 숫자 개수 구하기

문제 소개

이 문제에서는 모든 요소가 0으로 초기화된 크기 N의 배열과, 아래 형태의 Q개의 쿼리가 주어집니다.

update(s, e, val) → 이 쿼리는 인덱스 s부터 e까지(양 끝 포함)의 모든 요소를 val 값으로 갱신합니다.

우리가 구해야 할 것은 주어진 연산을 q번 적용한 뒤 배열에 존재하는 서로 다른 숫자의 개수입니다.

예시

입력 : N = 6, Q = 2
Q1 = update(1, 4, 3)
Q2 = update(0, 2, 4)

출력 : 3

설명

초기 배열 : arr[] = {0, 0, 0, 0, 0, 0}

쿼리 1 − update(1, 4, 3) → arr[] = {0, 3, 3, 3, 3, 0}

쿼리 2 − update(0, 2, 4) → arr[] = {4, 4, 4, 3, 3, 0}

최종 배열에는 4, 3, 0의 세 가지 서로 다른 값이 남으므로 정답은 3이 됩니다.

해결 접근 방법

가장 단순한 해결 방법은 각 쿼리를 배열에 직접 적용한 뒤, 별도의 자료구조를 이용해 서로 다른 값의 개수를 세어 반환하는 것입니다. 이 방법은 구현이 쉽다는 장점이 있지만, 쿼리 하나를 처리할 때마다 최악의 경우 O(N)의 시간이 소요되어 비효율적일 수 있습니다.

더 효율적인 해결책은 lazy propagation(지연 전파) 기법을 활용하여 쿼리에서 수행되는 범위 갱신 연산을 최적화하는 것입니다. 세그먼트 트리를 0으로 초기화하고, 갱신 연산이 실행될 때 해당 구간을 담당하는 노드에 값을 저장합니다. 이후 트리를 순회하면서 등장하는 값들을 집합(set)에 모으면, 배열에 남아 있는 서로 다른 숫자의 개수를 손쉽게 구할 수 있습니다. 지연 전파 덕분에 범위 갱신 연산의 성능이 크게 향상됩니다.

예제 코드

아래 프로그램은 위에서 설명한 해결 방법의 동작을 보여줍니다.

#include 
using namespace std;
#define N 100005
int lazyST[4 * N];
set diffNo;
void update(int s, int e, int val, int idx, int l, int r){
    if (s >= r or l >= e)
        return;
    if (s <= l && r <= e) {
        lazyST[idx] = val;
        return;
    }
    int mid = (l + r) / 2;
    if (lazyST[idx])
        lazyST[2 * idx] = lazyST[2 * idx + 1] = lazyST[idx];
    lazyST[idx] = 0;
    update(s, e, val, 2 * idx, l, mid);
    update(s, e, val, 2 * idx + 1, mid, r);
}
void query(int idx, int l, int r){
    if (lazyST[idx]) {
        diffNo.insert(lazyST[idx]);
        return;
    }
    if (r - l < 2)
        return;
    int mid = (l + r) / 2;
    query(2 * idx, l, mid);
    query(2 * idx + 1, mid, r);
}
int main() {
    int n = 6, q = 3;
    update(1, 3, 5, 1, 0, n);
    update(4, 5, 1, 1, 0, n);
    update(0, 2, 9, 1, 0, n);
    query(1, 0, n);
    cout<<"연산 후 배열에 존재하는 서로 다른 숫자의 개수는 "<
출력 결과
연산 후 배열에 존재하는 서로 다른 숫자의 개수는 3