알고리즘/Mo's 알고리즘
BOJ 백준 21064 Even Intervals
kyjdummy
2025. 5. 23. 22:44
문제 : https://www.acmicpc.net/problem/21064
[ 문제 요약 ]
- 배열이 주어지고, 쿼리가 주어집니다. 배열의 값은 유일성이 보장됩니다. 쿼리는 구간이 주어지는데 구간은 0번 인덱스부터 배열의 마지막 인덱스까지 주어질 수 있습니다.
- 이 때, 구간 안의 숫자들을 정렬했을 때, 짝수 번 인덱스의 모든 값들의 합을 쿼리마다 출력합니다. 인덱스는 0부터 시작합니다.
- 값은 10^9 + 7로 나눈 나머지를 출력합니다.
[ 테스트 케이스 설명 ]
5 5// 배열 원소 수(1<=50,000), 쿼리가 주어짐(1<=200,000)
2 4 10 16 6// 원소 값(유일성 보장) 0<=1,000,000,000
0 2// 쿼리가 주어짐 인덱스 0부터 시작
1 3
0 3
2 3
0 4
//해당 구간의 값들을 정렬했을 때, 짝수번 인덱스 위치에 있는 값들을 모두 더한 값 출력(INDEX는 0부터 시작)
12
20
12
10
24
[ 알고리즘 분류 ]
- 자료 구조
- 세그먼트 트리
- 오프라인 쿼리
- 값 / 좌표 압축
- mo’s 알고리즘
[ 문제 해설 ]
이 문제의 핵심은 짝수 번 인덱스의 합을 빠르게 구해오는 것에 있습니다. 일반 세그먼트 트리를 이용해서, 짝수 번 인덱스를 하나하나 구해오는 것은 시간제한이 20초로 길다 해도 시간 초과입니다.
그래서 세그먼트 트리 구현 시, 별도의 자료구조를 만들어야 합니다.
짝수 번 인덱스마다의 합을 구하기 위해 아래와 같은 세그먼트 트리 노드 구조를 생각할 수 있습니다.
class Node{
long cnt;// 현재까지 포함된 원소의 개수
long total;// 현재까지 포함된 원소의 값을 모두 더한 것
long even_sum;// 현재까지 포함된 원소의 짝수 인덱스 값을 모두 더한 것, (0부터 시작)
}
노드 안에,
(1) 현재까지 포함된 원소의 개수
(2) 현재까지 포함된 원소의 값을 모두 더한 값
(3) 현재까지 포함된 원소의 짝수 인덱스의 값을 모두 더한 것을 갖고 있게 합니다.
이 후, 부모 노드 생성 시 규칙을 두어 항상 해당 노드의 내용이 유지되도록 하면 됩니다.
먼저 cnt 값 갱신은, 단순히 왼쪽과 오른쪽 자식 노드의 모든 cnt를 합치면 됩니다. 마찬가지로 total도 모든 인자의 값을 합치면 됩니다.
짝수의 합 (even_sum)을 구하는 것은, 왼쪽 자식 노드의 cnt만 확인하면 됩니다.
예를 들어
왼쪽 자식 노드의 cnt가 짝수 면, 왼쪽 자식 노드의 even_sum과 오른쪽 자식 노드의 even_sum을 그냥 더하고,
왼쪽 자식 노드의 cnt가 홀수 면, 왼쪽 자식 노드의 even_sum은 그대로 더하지만, 오른쪽 자식 노드는 (오른쪽 자식 노드의 total)에서 (오른쪽 자식 노드의 even_sum)을 뺀 값을 더합니다.
이게 성립하는 이유는 아래와 같습니다.
- 왼쪽 자식 노드 인자들 : [ 1, 7 ]
- 오른쪽 자식 노드 인자들 : [ 8, 9, 13 ]
- 둘을 붙임 : [ 1, 7, 8, 9, 13 ]
왼쪽 노드에 오른쪽을 붙일 때, 왼쪽 자식 노드가 짝수 면 오른쪽 자식 노드도 짝수번째로 붙게 됩니다.(인덱스 0부터 시작함을 유념) 이와 반대로 왼쪽 자식 노드가 홀 수인 경우는 아래와 같습니다.
- 왼쪽 자식 노드 인자들 : [ 1, 7, 8 ]
- 오른쪽 자식 노드 인자들 : [ 9, 13, 20 ]
- 둘을 붙임 : [ 1, 7, 8, 9, 13, 20 ]
위와 같이 왼쪽 자식 노드가 홀 수면, 왼쪽과 오른쪽을 붙일 때, 오른쪽 자식 노드의 인자들 중 홀 수 번에 있는 인자들이 짝수 값이 됩니다. 그래서 오른쪽 자식 노드 계산은, total에서 even_sum을 빼어 홀수 번 인자들만을 구해와 더해주는 것입니다.
어떻게 보면 total 변수 존재 이유는 홀수번째 수들의 합을 구하기 위해서라고 할 수 있습니다.
세그먼트 트리의 idx는 정렬된 값 그 자체로 쓰이기 때문에 가능한 로직입니다.
아래 코드는 값 압축 + mo’s + 세그먼트 트리를 활용한 풀이입니다.
[ 정답 코드 ]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
class Main{
static final long MOD = 1_000_000_007;
static int N, Q;
static int arr[];// 주어지는 원소의 압축 값을 담을 배열
static int brr[];// 주어지는 원소의 압축 값을 원래대로 되돌리거나, 압축시 사용할 배열
static long ans[];// 최종 결과를 담을 배열
static Node tree[];// 세그먼트 트리
static List<Query> query;// 주어지는 쿼리를 담을 리스트
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());// 배열 원소 수(1<=50,000)
Q = Integer.parseInt(st.nextToken());// 쿼리가 주어짐(1<=200,000)
arr = new int[N];
brr = new int[N];
ans = new long[Q + 1];
tree = new Node[N * 4];
query = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++)
arr[i] = brr[i] = Integer.parseInt(st.nextToken());
for(int i=1, blockSize = (int)Math.sqrt(N); i<=Q; i++)
{
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
query.add(new Query(s, e, i, s / blockSize));
}
// mo's알고리즘을 위한 정렬
Collections.sort(query);
// 값 압축
Arrays.sort(brr);
for(int i=0; i<N; i++)
arr[i] = binarySearch(arr[i]);
// 세그먼트 트리 노드 초기화
for(int i=0; i<tree.length; i++)
tree[i] = new Node();
int s = 0;// 인덱스가 0부터 시작이라 s는 이미 0이 들어가있다 가정
int e = -1;// 인덱스가 0부터 시작이라 e는 -1부터 시작
for(Query q : query)
{
// 현재 arr[i]에 들어있는 값은 값 압축으로 인해 brr의 인덱스가 들어가있음
while(e < q.e) update(1, 0, N - 1, arr[++e], true);
while(q.s < s) update(1, 0, N - 1, arr[--s], true);
while(q.e < e) update(1, 0, N - 1, arr[e--], false);
while(s < q.s) update(1, 0, N - 1, arr[s++], false);
// 1에는 항상 현재 있는 모든 값들의 짝수 인덱스의 합이 들어가있음
ans[q.idx] = tree[1].even_sum % MOD;
}
StringBuilder sb = new StringBuilder();
for(int i=1; i<=Q; i++)
sb.append(ans[i]).append('\n');
System.out.print(sb);
}
static int binarySearch(int target) {
int s = 0;
int e = N - 1;
int res = 0;
while(s <= e)
{
int mid = (s + e) >> 1;
if(brr[mid] >= target)
{
e = mid - 1;
res = mid;
}
else
s = mid + 1;
}
return res;
}
static void update(int treeNode, int s, int e, int targetIdx, boolean isPlus) {
if(e < targetIdx || targetIdx < s)
return;
if(s == e)
{
if(isPlus)
{
// 값을 더하는 것이면 초기값 세팅
tree[treeNode].cnt = 1;
tree[treeNode].total = brr[targetIdx];
tree[treeNode].even_sum = brr[targetIdx];
return;
}
// 값을 빼는 것이면, 모든 값을 0으로 초기화
tree[treeNode].cnt = 0;
tree[treeNode].total = 0;
tree[treeNode].even_sum = 0;
return;
}
int mid = (s + e) >> 1;
int Lnode = treeNode << 1;
int Rnode = treeNode << 1 | 1;
update(Lnode, s, mid, targetIdx, isPlus);
update(Rnode, mid + 1, e, targetIdx, isPlus);
tree[treeNode].cnt = tree[Lnode].cnt + tree[Rnode].cnt;
tree[treeNode].total = tree[Lnode].total + tree[Rnode].total;
// 왼쪽 자식노드 원소의 개수가 짝수면, 오른쪽 자식노드의 even_sum을 그대로 더한다.
// 왼쪽이 짝수라 왼쪽 자식노드에 오른쪽 자식노드를 그대로 붙여도 상관없이 오른쪽이 짝수부터 시작임
if(tree[Lnode].cnt % 2 == 0)
tree[treeNode].even_sum = tree[Lnode].even_sum + tree[Rnode].even_sum;
// 왼쪽 자식노드 원소 수가 홀수면, 오른쪽 자식노드를 붙이면 한칸 뒤가 짝수기 때문에 오른쪽은 total - even_sum으로 하여
// 홀수 값을 더해준다.
else
tree[treeNode].even_sum =
tree[Lnode].even_sum + tree[Rnode].total - tree[Rnode].even_sum;
}
static class Query implements Comparable<Query>{
int s, e, idx, fac;
Query(int s, int e, int idx, int fac){
this.s = s;
this.e = e;
this.idx = idx;
this.fac = fac;
}
@Override
public int compareTo(Query o) {
// 구간이 다르면 구간기준 오름차순 정렬
if(fac != o.fac)
return fac - o.fac;
// 구간의 값이 짝수면 e기준 오름차순 정렬
if((fac & 1) == 0)
return e - o.e;
// 구간의 값이 홀수면 e기준 내림차순 정렬
return o.e - e;
}
}
static class Node{
long cnt;// 현재까지 포함된 원소의 개수
long total;// 현재까지 포함된 원소의 값을 모두 더한 것
long even_sum;// 현재까지 포함된 원소의 짝수 인덱스 값을 모두 더한것, (0부터 시작)
}
}