Sqrt Decompositon(평방분할) & Mo's Algorithm

BOJ8462) 배열의힘

먼저 이 문제를 살펴보자

* n개의 원소가 존재하고, [L,R] quer가 들어올 때 마다 부분 배열의 힘을 구하는 것이다.

* 여기서 Ks라 하면 자연수 s의 개수를 뜻하는데, 부분배열에서 이 모든 자연수 s에 대해 Ks * Ks * s 를 구하는 것이다.

=> 나이브하게 모든 query에 대하여 다 훑어본다면 O(N^2)의 시간복잡도를 갖는다.

이 때 Sqrt decompostion을 적용해보자.

Sqrt Decomposion이란?

* 간단하게 N개의 집합을 sqrt(N)개의 집합으로 나누어 값을 다룬다고 생각하면 되는데,

 이 문제에서는 query 에 적용하는 Query Sqrt Decompostion을 사용할 것이다.

또한 query에 대하여 분할 하는 것을 Mo's algorithm이라고 한다,

각각 query[L,R]에 대해서 L/sqrt(N)으로 정렬한다. 만약에 값이 같은경우, R 값을 그다음 키값으로 정렬한다. (오름차순)

정렬을 하게 되면 query의 순서가 뒤바뀌기 때문에 따로 index값을 저장해주어야 한다.

값을 변경하는 query (update query) 가 존재하는경우 이 알고리즘을 적용할 수 없다. 

대신, 구간의 특정 수의 개수를 구하는 거 같은 특수한 형태의 문제에는 아주 잘 적용된다.

결론적으로, N개의 원소가 존재하고 quert[L,R] 이 존재할 때, L/sqrt(N)과 R우선순위로 정렬 하게 된다면

theorem

1. N/sqrt(N) == sqrt(N)개의 집합이 형성된다.

2. 하나의 Block 내에서 query(L,R] -> [L',R']의 변화가 있다면,L'-L <= sqrt(N)이고 R <= R' 이다. 

3. 동일 Block내에서 R의 변화는 최대 N까지이므로, 최종적으로 모든 query에서의 R은 O(N^3/2) 시간복잡도 내에 변화한다.

4. 한 Block내에서 L의 range는 sqrt(N)이므로 최종적으로 모든 query에 대해서 L은 O(Q*sqrt(N)) 시간복잡도내에서 변화한다.

5. 그렇기 때문에 Mo's algorithm은 O((N+Q)*sqrt(N)*F) 의 시간 복잡도를 갖는다. (F는 L,R의 변화할 때마다 값을 처리해주는 함수를 만들었을 때, 그 함수의 처리 시간이다.)

이렇게 window size 로 정렬을 해주고.

현재의 알고있는 l값과 r값을 이용하여 꿈틀꿈틀 조정하게 되는데, 이 꿈틀꿈틀의 시간복잡도가 O(n*sqrt(n)) 인 것이다.

그러므로 구간합 구하기, 최대값 구하기 같은 유형의 문제들을 굳이 segment tree나 fenwick tree를 구현하지 않아도, 최초의 [L,R]을 설정해놓고 정렬된 query를 훑으면서 [L,R] ->[L',R']로의 query range를 확장,축소 해나가면 해결이 가능하다.

8462배열의힘 solution code

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
 
ll h;
struct dot{
    ll l,r,id;
 
    bool operator < (const dot& A) const{
        return l/h == A.l/h ? r < A.r : l/h < A.l<h;
    }
};
 
dot query[101000];
ll res[101000];
ll cnt[101000];
 
ll move(ll flag,ll val){
    cnt[val] += flag;
    return (2ll * flag *cnt[val] - 1)*val;
}
ll n,k,l,r;
ll sum;
int main(){
    scanf("%lld %lld",&n,&k);
 
    h = sqrt(n);
 
    vector<ll> a(n+1,0);
 
    for(int i = 1; i <= n ; i++)
        scanf("%lld",&a[i]);
 
    for(int i = 0 ; i < k; i++){
        scanf("%lld %lld",&query[i].l,&query[i].r);
        query[i].id = i;
    }
 
    sort(query,query+k);
 
    l = query[0].l;
    r = query[0].r;
    for(int i = l; i<= r; i++){
        sum += move(1,a[i]);
    }
 
    
    res[query[0].id] = sum;
 
    for(int i = 1; i < k ; i++){
        while(l > query[i].l) sum += move(1,a[--l]);
        while(l < query[i].l) sum += move(-1,a[l++]);
        while(r > query[i].r) sum += move(-1,a[r--]);
        while(r < query[i].r) sum += move(1,a[++r]);
        res[query[i].id] = sum;
    }
 
    for(int i = 0 ; i < k ; i++){
        printf("%lld\n",res[i]);
    }
}