티스토리 뷰
Table of Contents
1. 개요
https://www.acmicpc.net/problem/13547
먼저 위의 문제를 읽어주시길 바랍니다.
범위 쿼리를 처리하는 상황에서 가끔 이런 상황들이 있습니다. 배열 Array[1...N], 함수 Function, 범위 [L, R] 이 주어질 때
Function(Array[L], Array[L+1], ..., Array[R]) 계산하는데, 배열에 저장된 값을 고치는 update 연산은 없는 상황입니다. 위의 문제가 그 예시이지요.
이런 상황을 만나면 Segment tree 나 Sparse table 로 접근하는 경우가 많습니다. 하지만 이 두 자료구조를 활용한 접근은 대체로, 온라인 처리가 아닌 배치 처리가 가능하다는 점을 사용하지 않습니다. 즉, 만일 이런 문제를 Segment tree 나 Sparse table 로 푼다면, 쿼리들의 순서에 상관 없이 답을 구할 수 있는 프로그램까지 짠 후, 굳이 주어진 쿼리 순서대로 답을 구해주는 꼴이 되는 것입니다.
그런 점에서 착안해 배치 처리인 점을 먼저 공략하면, 풀 수 없던 문제를 풀거나 좀 더 쉬운 방법으로 문제를 풀 수 있는 경우가 있습니다. 이 때 사용하는 것이 Mo's algorithm 입니다.
2. 쿼리 처리
Mo's algorithm 의 기본적인 아이디어는 배치 처리의 활용입니다. 즉, 쿼리의 순서를 마음대로 조작할 수 있다는 점을 이용합니다. 그렇다면 쿼리의 답을 구할 때, 이전 쿼리를 처리할 때 얻은 정보의 활용법을 고민해보는 건 당연한 수순일 것입니다.
한 번 개요에 있는 문제에서 [Li, Ri] 에 대한 답을 통해, [L(i+1), R(i+1)] 을 구해보겠습니다. [Li, Ri] 에서 구한 서로 다른 수의 개수 만으로는 [L(i+1), R(i+1)] 에서의 답을 빠르게 구하기 힘들다는 건 금방 알 수 있습니다. [Li, Ri] 안에 어떤 수가 얼마나 있었느냐 에 따라 경우의 수가 나뉘기 때문이지요. 따라서 '[Li, Ri] 안에 어떤 수가 얼마나 있었느냐' 에 대한 정보를 추가로 저장해야 합니다.
COUNT[x] = ((A[j] == x) 인 j 의 갯수)
-> COUNT[x] >= 1 이면 구간 안에 x가 존재하며, COUNT[x] == 0 이면 구간 안에 x가 존재하지 않는다는 의미가 됩니다.
[Li, Ri] 에 대해 위와 같은 배열이 저장되어 있다면, O( | L(i+1) - Li | + | R(i+1) - Ri | ) 번의 연산으로 답을 구할 수 있습니다. [Li, Ri] 에서 [L(i+1), R(i+1)] 로 구간을 확장해 가면서, COUNT 배열을 갱신하면, '서로 다른 수의 갯수'도 같이 갱신할 수 있기 때문입니다. COUNT[x] 가 0에서 1로 갱신되면 '서로 다른 수의 개수'가 1 증가했다는 걸 알 수 있고, COUNT[x] 가 1에서 0으로 갱신되면 '서로 다른 수의 개수'가 1 감소했다는 걸 알 수 있지요. 자세한 방법은 아래 코드를 참고해주시길 바랍니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
// code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#define PII pair<int,int>
#define PIII pair<PII,int>
using namespace::std;
const int N = 100005, M = 1000005, SQRT_N = 300;
PII query[N];
PIII order[N];
int cnt[M];
int a[N];
int n,q;
int an;
int ans[M];
void add(int idx){
if(cnt[a[idx]]==0) an++; // 이번 추가로 새로운 수가 생김
cnt[a[idx]]++;
}
void erase(int idx){
cnt[a[idx]]--;
if(cnt[a[idx]]==0) an--; // 이번 삭제로 한 수가 모두 사라짐
}
void go_query(PII prev, PII now){
int l1 = prev.first;
int r1 = prev.second;
int l2 = now.first;
int r2 = now.second;
for(int i = l1-1; i>=l2; i--) add(i); // l1 > l2 인 경우, 구간이 늘어났으므로 노드 추가
for(int i = r1+1; i<=r2; i++) add(i); // r1 < r2 인 경우, 구간이 늘어났으므로 노드 추가
for(int i = l1; i<l2; i++) erase(i); // l1 < l2 인 경우, 구간이 줄었으므로 노드 삭제
for(int i = r1; i>r2; i--) erase(i); // r1 > r2 인 경우, 구간이 줄었으므로 노드 삭제
}
|
cs |
이처럼 a 에 이전 쿼리의 정답, cnt[x] = ((A[j] == x) 인 j 의 갯수) 이 저장되어 있다면 go_query([Li, Ri], [L(i+1), R(i+1)]) 을 통해 답을 갱신할 수 있습니다. ( * O( | L(i+1) - Li | + | R(i+1) - Ri | ) )
하지만 아직 총 시간복잡도는 O(N^2) 으로 머물러 있습니다. 여기에서 시간복잡도를 줄이는 것은 배치 처리를 얼마나 활용하느냐, 즉, 쿼리를 어떻게 잘 정렬하는 지에 달려있습니다.
3. 쿼리 정렬
위에서 구한 go_query() 함수를 활용하려면 'O( | L(i+1) - Li | + | R(i+1) - Ri | ) 의 합' 을 줄여야 합니다. 방법은 생각보다 간단한데, query를 { Li / sqrt(n) , Ri } 을 기준으로 정렬하면 끝입니다.
( * Li / sqrt(n) 을 기준으로 정렬, 만일 Li / sqrt(n)가 같다면 Ri 를 기준으로 정렬 )
시간 복잡도를 알아보기 위해 먼저 O( | L(i+1) - Li | ) 의 총합을 알아보겠습니다.
(1) Li / sqrt(n) == L(i+1) / sqrt(n) 인 경우
Li / sqrt(n) == L(i+1) / sqrt(n) 이기 때문에, O( | L(i+1) - Li | ) <= sqrt(n) 임은 당연합니다.
-> (1) 의 경우를 모두 합해도 O( Q * sqrt(N) ) 이 됩니다. ( * Q = 쿼리의 갯수 )
(2) Li / sqrt(n) != L(i+1) / sqrt(n) 인 경우
이런 경우는 최대 sqrt(n) 번 등장할 수 있습니다.( Li / sqrt(n) = 0 ~ sqrt(n) 만 가능하기 때문. )
| L(i+1) - Li | 의 최댓값은 N-1 입니다.
-> (2) 의 경우를 모두 합해도 O( N * sqrt(N) ) 이 됩니다.
이제 O( | R(i+1) - Ri | ) 의 총합을 알아보겠습니다.
(1) Ri, R(i+1), R(i+2), ..., Rj가 한 블록 (Li / sqrt(n)가 모두 동일) 인 경우
R이 오름차순으로 정렬되어 있기 때문에 한 블록에서 | R(i+1) - Ri |의 총합은 Rj - Ri 입니다. 이는 N이하입니다.
그리고 블록은 총 sqrt(N)개 까지 있을 수 있습니다.
-> (1) 의 경우를 모두 합해도 O( N * sqrt(N) ) 이 됩니다.
(2) Li / sqrt(n) != L(i+1) / sqrt(n) 인 경우
이런 경우는 최대 sqrt(n) 번 등장할 수 있습니다.( Li / sqrt(n) = 0 ~ sqrt(n) 만 가능하기 때문입니다. )
| R(i+1) - Ri |은 N이하입니다.
-> (2) 의 경우를 모두 합해도 O( N * sqrt(N) ) 이 됩니다.
위의 내용을 종합하면, 총 시간복잡도 = Q( (N+Q) * sqrt(N) * f(x) ) 임을 알 수 있습니다.
( * f(x) = add() 와 erase() 함수의 시간 복잡도, 이 예제에서는 O(1)입니다.)
직관적으로 이해하기 위해선 이 쿼리들을 (x, y) = (Li, Ri) 인 점으로 2차원 좌표계에 찍어보면 편합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
// code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#define PII pair<int,int>
#define PIII pair<PII,int>
using namespace::std;
const int N = 100005, M = 1000005, SQRT_N = 300;
PII query[N];
PIII order[N];
int cnt[M];
int a[N];
int n,q;
int an;
int ans[M];
void add(int idx){
if(cnt[a[idx]]==0) an++; // 이번 추가로 새로운 수가 생김
cnt[a[idx]]++;
}
void erase(int idx){
cnt[a[idx]]--;
if(cnt[a[idx]]==0) an--; // 이번 삭제로 한 수가 모두 사라짐
}
void go_query(PII prev, PII now){
int l1 = prev.first;
int r1 = prev.second;
int l2 = now.first;
int r2 = now.second;
for(int i = l1-1; i>=l2; i--) add(i); // l1 > l2 인 경우, 구간이 늘어났으므로 노드 추가
for(int i = r1+1; i<=r2; i++) add(i); // r1 < r2 인 경우, 구간이 늘어났으므로 노드 추가
for(int i = l1; i<l2; i++) erase(i); // l1 < l2 인 경우, 구간이 줄었으므로 노드 삭제
for(int i = r1; i>r2; i--) erase(i); // r1 > r2 인 경우, 구간이 줄었으므로 노드 삭제
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
scanf("%d",&q);
for(int i=1; i<=q; i++){
scanf("%d %d",&query[i].first, &query[i].second);
order[i].first = PII(query[i].first/SQRT_N, query[i].second);
order[i].second = i;
}
sort(order+1, order+q+1);
for(int i=1; i<=q; i++){
go_query(query[order[i-1].second], query[order[i].second]);
ans[order[i].second] = an;
}
for(int i=1; i<=q; i++)
printf("%d\n",ans[i]);
return 0;
}
|
cs |
4. 문제
(0)
풀이 : 본문 참고
(2) [BOJ 8462] 배열의 힘
※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.
※ 문의 : rikang93@gmail.com
'범위 쿼리 처리 ( Range Query )' 카테고리의 다른 글
트리에서의 모스 알고리즘 활용 ( Mo's algorithm on tree ) (0) | 2017.11.03 |
---|---|
스파스 테이블 ( Sparse table ) (0) | 2017.11.02 |