연속된 가로등들이 각각 고유한 색상을 가지고 있을 때, 특정 색상의 모든 가로등을 반복적으로 켜고 끄는 연산을 수행한다. 각 연산 후 현재 켜진 가로등들이 형성하는 최대 연속 구간의 개수를 효율적으로 계산하는 문제를 다룬다.

핵심 아이디어

연속 구간의 개수는 다음과 같이 표현할 수 있다:

연속 구간 수 = (켜진 가로등 총 개수) − (인접한 켜진 가로등 쌍의 수)

따라서 두 가지 값을 동적으로 관리하면 된다:

• totalOn: 현재 켜진 가로등의 총 개수
• adjPairs: 인접한 위치의 가로등이 모두 켜진 쌍의 개수

빈도 기반 분류 전략

색상별 등장 횟수를 기준으로 임계값 T = √n을 설정하여 두 그룹으로 분류한다:

고빈도 색상은 최대 n/T = √n개 존재하므로, 색상 간 영향도를 O((√n)²) 공간에 저장 가능하다.

데이터 구조 설계

// 색상별 위치 목록
vector<int> locations[COLOR_MAX];

// 고빈도 색상에 할당된 고유 ID
int heavyId[COLOR_MAX];

// 고빈도 색상 간 인접 쌍 개수 (무향 그래프)
int crossEffect[MAX_HEAVY][MAX_HEAVY];

// 각 고빈도 색상의 기여도
int heavyBase[MAX_HEAVY];      // 같은 색상 내 인접 기여
int heavyCross[MAX_HEAVY];     // 다른 고빈도 색상과의 인접 기여

// 현재 켜진 상태 여부
bool isActive[COLOR_MAX];

전처리 단계

int threshold = sqrt(n);
int heavyCount = 0;

// 고빈도 색상 식별 및 ID 할당
for (int color = 1; color <= m; ++color) {
    if (frequency[color] >= threshold) {
        heavyId[color] = ++heavyCount;
    }
}

// 고빈도 색상 간 인 관계 계산
for (int i = 2; i <= n; ++i) {
    int left = heavyId[lampColor[i-1]];
    int right = heavyId[lampColor[i]];
    if (left && right) {
        crossEffect[left][right]++;
        crossEffect[right][left]++;
    }
}

쿼리 처리 로직

켜기 연산 (활성화)

void activate(int color) {
    isActive[color] = true;
    totalOn += frequency[color];
    
    if (heavyId[color]) {
        int hid = heavyId[color];
        // 이 색상이 받는 영향을 adjPairs에 반영
        adjPairs += heavyBase[hid] + heavyCross[hid];
        
        // 다른 고빈도 색상에 이 색상의 영향을 전파
        for (int other = 1; other <= heavyCount; ++other) {
            if (other != hid) {
                heavyCross[other] += crossEffect[hid][other];
            }
        }
    } else {
        // 저빈도: 직접 인접 위치 확인
        for (int pos : locations[color]) {
            if (pos > 1) checkNeighbor(pos - 1, +1);
            if (pos < n) checkNeighbor(pos + 1, +1);
        }
    }
}

끄기 연산 (비활성화)

void deactivate(int color) {
    isActive[color] = false;
    totalOn -= frequency[color];
    
    if (heavyId[color]) {
        int hid = heavyId[color];
        adjPairs -= heavyBase[hid] + heavyCross[hid];
        
        for (int other = 1; other <= heavyCount; ++other) {
            if (other != hid) {
                heavyCross[other] -= crossEffect[hid][other];
            }
        }
    } else {
        for (int pos : locations[color]) {
            if (pos > 1) checkNeighbor(pos - 1, -1);
            if (pos < n) checkNeighbor(pos + 1, -1);
        }
    }
}

인접 확인 헬퍼

void checkNeighbor(int neighborPos, int delta) {
    int neighborColor = lampColor[neighborPos];
    if (isActive[neighborColor]) {
        adjPairs += delta;
    }
    if (heavyId[neighborColor]) {
        heavyBase[heavyId[neighborColor]] += delta;
    }
}

답 출력

// 각 쿼리 후
cout << (totalOn - adjPairs) << '\n';

복잡도 분석

이 방식으로 10⁵ 제약 조건에서 효율적으로 동작한다.