스위핑 라인은 데이터 구조를 활용한 중요한 기법으로, 주로 구간 내 부분 구간의 정보를 쿼리하는 문제를 해결할 때 사용됩니다. 이 기법은 오프라인 처리 기반으로 동작합니다.
기본 아이디어는 다음과 같습니다. 모든 쿼리를 오프라인으로 저장한 후 특정 기준으로 정렬합니다. 그런 다음 배열의 시작부터 끝까지(1부터 n까지) 순회하면서 정보를 점진적으로 업데이트합니다. 특정 시점(예: 쿼리의 오른쪽 끝점에 도달했을 때)에서 해당 쿼리의 답을 계산하여 결과 배열에 저장합니다.
한 고수의 설명에 따르면, "스위핑 라인은 한 축을 시간 축으로 간주하고, 데이터 구조를 사용해 시간이 지남에 따라 변화하는 상태를 관리하는 기법"입니다. 이는 수정과 쿼리가 동시에 진행되는 과정을 직관적으로 설명합니다. 결과적으로 수정 n번, 쿼리 m번을 처리하며 전체 시간 복잡도는 O((n+m) log n)입니다.
기본 코드 템플릿은 매우 간단합니다:
for (int i = 1, j = 1; i <= n; ++i) {
update(); // 현재 위치 기반 정보 업데이트
while (j <= m && q[j].r == i) {
ans[q[j].id] = query(); // 쿼리 처리
++j;
}
}
P9991 Ynoi Easy Round 2023 TEST_107 문제 분석
극대 부분 구간의 특성을 세 가지 경우로 나누어 고려합니다:
[l', r'] = [l, i]:a_{i+1} = x이고,[l, i]구간 내에x가 없는 경우[l', r'] = [i, r]:a_{i-1} = x이고,[i, r]구간 내에x가 없는 경우l' > l, r' < r:a_{l'-1} = a_{r'+1} = x이고,[l', r']구간 내에x가 없는 경우
첫 번째 경우를 처리하기 위해 las[i]를 이전 위치 배열로 정의합니다. 스위핑 라인이 i를 지나갈 때마다 세그먼트 트리의 las[i] 위치를 i로 업데이트합니다. 쿼리 j의 오른쪽 끝점이 r_j = i일 때, 세그먼트 트리 구간 [0, l_j - 1]의 최댓값이 첫 번째 경우에 해당하는 i를 나타냅니다.
두 번째 경우는 배열과 쿼리를 모두 뒤집어(역순) 첫 번째 경우와 동일한 로직을 적용합니다. 세 번째 경우는 i를 처리할 때 las[i] 위치에 (i-1) - (las[i]+1) + 1 값을 업데이트하고, 쿼리 구간 [l_j, r_j]의 최댓값을 직접 조회합니다.
구체적인 스위핑 라인 구현 예시 (첫 번째 경우):
for (int i = 1, j = 1; i <= n; ++i) {
update(1, 0, n, las[i], i); // las[i] 위치를 i로 갱신 (0 인덱스 주의)
while (j <= m && q[j].r == i) {
ans[q[j].id] = max(ans[q[j].id], query(1, 0, n, 0, q[j].l - 1) - q[j].l);
++j;
}
}
GSS2 - Can you answer these queries II
이 문제는 GSS1과 달리 부분 구간을 고려해야 하므로, 오프라인 스위핑 라인 기법을 적용합니다. 핵심 트릭은 세그먼트 트리의 각 리프 노드가 i로 시작하는 최대 부분합을 나타내도록 하는 것입니다. las[i] + 1부터 i까지 구간에 a[i]를 더하면, 중복된 값의 기여 구간이 서로 겹치지 않음을 보장합니다. 또한 구간의 역사적 최댓값을 유지하기 위해, 역사적 최댓값 태그를 함께 관리해야 합니다.
P9990 Ynoi Easy Round 2023 TEST_90 문제 분석
이 문제는 부분 구간의 개수를 세는 것이 핵심입니다. 스위핑 라인을 사용할 때, 세그먼트 트리에 저장된 역사적 버전의 합을 기록하는 트릭을 사용합니다. 스위핑 라인이 진행되면서 새로운 원소의 기여가 추가되면, 오른쪽 끝점의 범위가 현재 i까지 확장됩니다. 따라서 모든 구간의 답의 합은 모든 역사적 버전의 합과 같습니다.
각 숫자의 기여를 분석합니다. 특정 숫자가 영향을 미치는 구간은 [las[i] + 1, i]이며, 이 기여는 모든 구간 답의 홀짝성을 반전시킵니다. 답을 계산하기 위해 각 노드에서 답이 0 또는 1인 구간의 개수가 통계된 횟수를 각각 t0와 t1로 기록합니다. 각 구간의 답은 이 두 태그에 해당하는 구간 개수를 곱하여 계산됩니다. 매 수정 시 [1, n] 전체에 대해 t[1].t1++ 및 t[1].ans += t[1].sum1을 추가로 수행하여, 이 t1 값이 전체 트리로 전파되도록 합니다.
CF522D 문제 분석
이 문제는 스위핑 라인의 기본적인 활용 예시입니다. las[i] 위치를 i - las[i] 값으로 업데이트한 후, 쿼리 구간 내 최솟값을 조회하면 문제가 해결됩니다.