cgiosy.dev
Mo's Algorithm 본문
$k$차원 평면에서 점 $N$개, 초직사각형 $Q$개가 주어진다. 단, 각 초직사각형에 대해 원소가 $\infty$ 혹은 $-\infty$로만 이뤄진 점이 하나 존재해야 한다.
주어진 점 집합에 단일 점을 추가하는 어떤 연산 $*$에 대해, 각 초직사각형 내부의 점들을 해당 연산으로 합친 결과를 구해야 한다. 여기서 모스(Mo's) 알고리즘을 사용하면, 특정 연산들을 사용 가능할 때 $O(NQ^{1 - \frac{1}{k}})$ 정도에 문제를 해결할 수 있다.
2차원
모스 알고리즘이 가장 자주 사용되는 상황으로 예를 들어보자. 크기 $N$의 배열 $A$와 $[l, r]$ 구간 쿼리 $Q$개가 주어진다. 그러면 2차원 평면에서 $A$의 $i$번째 원소는 좌표 $(i, i)$에 위치하며 값 $A_i$를 가진 점으로, $t$번째 쿼리는 한 쪽 점이 $(\infty, -\infty)$이고 다른 쪽 점이 $(l_t, r_t)$인 직사각형으로 해석할 수 있다. 이 때 모스 알고리즘은 다음과 같은 로직으로 진행된다.
- 배열을 크기 $B$의 구간으로 쪼개고 각 구간을 버킷이라 부르자. $[l, r]$ 구간 쿼리들에 대해, $l$이 속한 버킷의 번호를 $b$라 하겠다.
- $b$가 동일한 쿼리들은 $r$을 기준으로 정렬한다. 이러면 각 버킷에 대해 $r$은 감소하지 않으므로, 제거 없이 추가만 하면 된다.
- $l$은 동일 버킷에 속할 뿐 감소할 수 있으므로 $b$번 버킷에 속한 값들은 별도로 다뤄야 한다. 버킷의 크기는 $B$ 이하이니 $Q$개의 쿼리마다 나이브하게 $B$개를 추가하여 답을 구하고, 추가 전으로 복구하면 된다.
- 이를 각 버킷에 대해 상태를 초기화해준 뒤 처리한다.
이 때 복구 $Q$번, 초기화 $\min(Q, \frac{N}{B})$번, 추가 $QB$번이 일어난다. 만약 복구 연산과 초기화의 시간복잡도가 $O(B)$, 추가가 $O(1)$이라면 $B$의 최적값은 $\frac{N}{\sqrt{Q}}$이고, 최종 시간복잡도는 $O(N\sqrt{Q})$가 된다.
코드
BOJ 13548. 수열과 쿼리 6을 버킷을 명시적으로 사용해 푼 코드이다. 버킷 크기는 256이다.
위에서 $B$의 최적값을 $\frac{N}{\sqrt{Q}}$라고 했지만 사실 정확히 저 값을 잡는 경우는 실제론 많지 않다. 우선 대놓고 모스를 쓰는 문제는 보통 $N = Q$기도 하고, 연산 간 상수 차이 때문에 저 근처의 적당한 값을 잡는 경우가 많다. 문제를 풀 땐 보통 구현의 편의성을 위해 $2^k$를 버킷 크기로 잡는 편이다.
#include <bits/stdc++.h>
using namespace std;
struct query {
int l, r, k;
bool operator<(query const R) const {
int a=l|255, b=R.l|255;
return a<b || a==b && r<R.r;
}
};
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int N, Q;
cin>>N;
int A[N];
for(int&x:A) cin>>x;
cin>>Q;
query B[Q];
for(int i=0; i<Q; i++) {
auto&[l,r,k]=B[i];
cin>>l>>r, --l, --r, k=i;
}
sort(B, B+Q);
int C[100001], Res[Q];
int s=0, e, v=0;
auto add=[&](int i) {
v=max(v, ++C[A[i]]);
};
auto del=[&](int i) {
--C[A[i]];
};
for(auto[l,r,k]:B) {
if(int t=l|255; s!=t) {
s=e=t, v=0;
memset(C, 0, sizeof(C));
}
while(e<r) add(++e);
int t=min(s, r), pv=v;
for(int i=t; i>=l; i--) add(i);
for(int i=l; i<=t; i++) del(i);
Res[k]=v;
v=pv;
}
for(auto x:Res) cout<<x<<'\n';
}코드 (암시적 버킷)
사실 복구와 초기화를 더 강한 연산인 '제거 연산' $QB$번으로 퉁치면 기존에 잘 알려진 방법이 된다. 이는 버킷을 암시적으로 다룰 수 있는 대신 2021 ICPC A. Best Student처럼 제거 연산(역연산)이 존재하지 않는 문제를 풀기 어려워진다.
다만 위에서 예로 든 수열과 쿼리 6의 경우, 제거 연산이 아주 쉽게 지원되기 때문에 어떤 방식으로든 풀 수 있다. 아래 코드가 예시이며, 속도는 그리 차이나지 않는다. 버킷 크기는 512이다.
#include <bits/stdc++.h>
using namespace std;
struct query {
int l, r, k;
bool operator<(query const R) const {
int a=l>>9, b=R.l>>9;
return a<b || a==b && (a&1 ? r>R.r : r<R.r);
}
};
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int N, Q;
cin>>N;
int A[N];
for(int&x:A) cin>>x;
cin>>Q;
query B[Q];
for(int i=0; i<Q; i++) {
auto&[l,r,k]=B[i];
cin>>l>>r, --l, --r, k=i;
}
sort(B, B+Q);
int C[100001]{}, D[N+1]{}, Res[Q];
int s=0, e=-1, v=0;
auto add=[&](int i) {
v+=!D[++C[A[i]]]++;
};
auto del=[&](int i) {
v-=!--D[C[A[i]]--];
};
for(auto[l,r,k]:B) {
while(l<s) add(--s);
while(e<r) add(++e);
while(s<l) del(s++);
while(r<e) del(e--);
Res[k]=v;
}
for(auto x:Res) cout<<x<<'\n';
}정렬 방식이 살짝 다른 것을 볼 수 있는데, 아래에서 설명한다.
팁
- $\infty$와 $-\infty$로만 이뤄진 점에 대해서, 두 값은 방향을 의미한다. 가령 위 예시에서 $(\infty, -\infty)$와 $(l, r)$의 의미는 $l \le x_i \wedge y_i \le r$인 점들을 직사각형에 포함하겠단 의미이다.
- 만약 두 번째 원소를 $\infty$로 바꿔서, $(\infty, \infty)$와 $(l, r)$의 경우 $l \le x_i \wedge r \le y_i$인 점들을 포함한다.
- 버킷 크기는 많은 상황에서 512나 256정도가 가장 빠른 것 같다.
- 암시적 버킷 형태로 풀 때 버킷의 번호가 짝수면 $r$이 단조증가, 홀수면 단조감소하도록 정렬하면 좀 더 빠르다. 다른 버킷으로 넘어갈 때마다 $r$을 싹 감소시켜버리는 대신, 직전 버킷에서의 결과를 사용하기 때문이다.
- 복구는 이전과 달라진 부분들을 다시 이전 값으로 되돌리는 것으로 생각할 수 있다. 보통 바뀔 예정인 값들(특히 쿼리의 답)을 미리 저장해놓고, 복구는 해당 값들로 다시 바꾸면 된다.
- 모든 값을 저장하고 복구하긴 힘들 수 있다. 이것들만 제거 연산으로 빼는 것을 고려하자. 다행히 복구 연산이 없을 때에 비해 관리해야 할 상태가 적으므로 한결 수월하다. 제거할 때 영향이 미치는 값들 중 일부는 복구로 인해 제거와 독립적으로 처리되기 때문이다.
- 혹은 아예 버킷에 속한 값을 부저장소에서 따로 관리할 수도 있겠다. 하지만 모스를 사용하게 되는 이유 자체가 평방분할조차 불가능한, 즉 저장소의 분리가 매우 까다로운 경우이기에 저게 가능한 상황은 거의 보지 못한 것 같다.
3차원
2차원 때와 비슷한 예를 들어보겠다. 기존과 비슷하지만 쿼리에 더해, 어떤 점을 추가하는 업데이트가 존재할 수 있다고 하자. 이 경우 초기 $A$의 점의 위치는 $(i, i, 0)$으로, $t$번째 쿼리가 구간 쿼리일 경우 $(\infty, -\infty, -\infty)$과 $(l_t, r_t, t)$로 이뤄진 직사각형으로, $t$번째 쿼리가 업데이트일 경우 $(k_t, k_t, t)$ 위치에 점을 추가하는 것으로 해석할 수 있다.
(작성 중)