백준 수열과 쿼리 18 (BOJ 14504), 수열과 쿼리 1.5 (BOJ 17410) 풀이 (제곱근 분할법)

제곱근 분할법을 이용하여 쿼리들을 처리하는 문제들을 풀이해봅시다.

참고로 다음에 다룰 두 문제는 쿼리의 순서, 변수의 범위만 다르고 풀이 방법은 거의 동일한 문제입니다. (시간 제한의 차이가 존재하긴 합니다.)

 

 

백준 BOJ 14504번 : 수열과 쿼리 18

 

 

위와 같이 특정 원소를 바꾸거나, 주어진 구간에서 특정 값보다 큰 원소의 개수를 구하는 쿼리들을 처리하는 문제입니다.

원소의 개수와 쿼리의 개수 모두 10만이므로, O(N^2)에는 당연히 풀이가 불가능합니다.

제곱근 분할법(Square-root Decomposition)을 사용하면 O(M√N log √N) 시간에 모든 쿼리를 처리할 수 있으므로 대략 1억번 정도의 연산으로 풀이할 수 있고, C++은 연산 속도가 빠른 편이므로 제한 시간 2초 안에 충분히 통과할 수 있습니다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> v;
vector<vector<int>> u;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    v.resize(N);
    for(int i=0; i<N; i++) cin >> v[i];

    int S = sqrt(N); u.resize(N/S + 1);
    for(int i=0; i<N; i++) u[i/S].push_back(v[i]);

    for(int i=0; i<u.size(); i++) sort(u[i].begin(), u[i].end());

    int M; cin >> M;

    while(M--) {
        int Q; cin >> Q;

        if(Q == 1) {
            int l, r, val; cin >> l >> r >> val;
            l--, r--;

            int cnt = 0;

            while(l % S != 0 && l <= r)
                if(v[l++] > val) cnt++;

            while((r + 1) % S != 0 && l <= r)
                if(v[r--] > val) cnt++;

            while(l <= r) {
                cnt += u[l/S].end() - upper_bound(u[l/S].begin(), u[l/S].end(), val);
                l += S;
            }

            cout << cnt << "\n";
        }
        else if(Q == 2) {
            int idx, val; cin >> idx >> val;
            idx--;

            u[idx/S].erase(lower_bound(u[idx/S].begin(), u[idx/S].end(), v[idx]));
            u[idx/S].insert(lower_bound(u[idx/S].begin(), u[idx/S].end(), val), val);

            v[idx] = val;
        }
    }
}

 

핵심 아이디어는 각 bucket 내에 있는 원소들을 정렬해주고, 특정 원소보다 큰 원소의 개수를 bucket.end() - upper.bound(bucket.begin(), bucket.end(), val)과 같은 식으로 구해주는 것입니다.

 

다만 이 경우 원소를 업데이트 할 때도 크기순으로 정렬이 되어야하므로 기존 원소에 해당하는 bucket을 찾고, 그 bucket에서 해당 원소를 이분탐색으로 찾아 제거해주고, 다시 이분탐색으로 새 원소의 크기에 맞는 위치를 찾아 넣어주는 귀찮은 과정을 거쳐야합니다.

lower_bound를 사용하면 log 시간에 원소의 탐색이나 크기 비교에 의한 위치 탐색이 가능하므로, bound 함수를 잘 활용해줍시다.

 

 

 

제출해보면 1초가 넘어가는 시간이므로 연산 횟수가 대충 1억 번은 넘어감을 알 수 있습니다.

제곱근 분할법이 해당되는 루트 시간은 로그 시간보다는 훨씬 많이 걸리므로 주어진 변수의 범위를 대충 계산해봐야 합니다.

 

주어진 시간 제한과 테스트케이스의 배치가 심각한 경우 다음 문제와 같은 경우도 발생할 수 있습니다.

 

 

백준 BOJ 17410번 : 수열과 쿼리 1.5

 

 

보시면 알겠지만 수열과 쿼리 18과 문제가 거의 동일합니다.

달라진 점은 시간 제한과 변수의 범위, 쿼리의 순서 정도입니다.

그렇다면 위의 풀이에서 쿼리 순서만 바꿔준 코드를 제출하면 통과가 가능할까요?

 

 

 

시간 초과가 발생합니다.

이론적으로는 문제가 없는 것 같은데, 풀이 시간을 줄이려면 어떻게 해야 할까요?

 

처리 시간에 문제가 되는 쿼리는 구간 합을 구해야 하는 2번 쿼리입니다.

제곱근 분할법 알고리즘의 원리에 대해 생각해보면 어느 정도까지는 bucket의 사이즈가 커질수록 처리 시간이 줄어듦을 알 수 있습니다.

따라서 bucket의 사이즈를 sqrt(N)으로 설정하는 것이 아닌, N이 10만이라고 하였으므로 sqrt(100000)에 해당하는 약 316보다 넉넉히 크게 잡아서 한 1000 정도로 잡아봅시다.

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> v;
vector<vector<int>> u;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    v.resize(N);
    for(int i=0; i<N; i++) cin >> v[i];

    int S = 1000; u.resize(N/S + 1);
    for(int i=0; i<N; i++) u[i/S].push_back(v[i]);

    for(int i=0; i<u.size(); i++) sort(u[i].begin(), u[i].end());

    int M; cin >> M;

    while(M--) {
        int Q; cin >> Q;

        if(Q == 1) {
            int idx, val; cin >> idx >> val;
            idx--;

            u[idx/S].erase(lower_bound(u[idx/S].begin(), u[idx/S].end(), v[idx]));
            u[idx/S].insert(lower_bound(u[idx/S].begin(), u[idx/S].end(), val), val);

            v[idx] = val;
        }
        else if(Q == 2) {
            int l, r, val; cin >> l >> r >> val;
            l--, r--;

            int cnt = 0;

            while(l % S != 0 && l <= r)
                if(v[l++] > val) cnt++;

            while((r + 1) % S != 0 && l <= r)
                if(v[r--] > val) cnt++;

            while(l <= r) {
                cnt += u[l/S].end() - upper_bound(u[l/S].begin(), u[l/S].end(), val);
                l += S;
            }

            cout << cnt << "\n";
        }
    }
}

↑  풀이 코드입니다. 달라진 부분은 S = sqrt(N)이 S = 1000으로 바뀐 점뿐입니다.

 

 

 

제출해보면 1.5초라는 시간 안에 아슬아슬하게 통과됨을 확인할 수 있습니다.

이론적으로는 bucket의 크기가 커질수록 수행 시간이 빨라져야 하지만, 단순 시간 복잡도만으로는 고려되지 않는 시간적 변수들이 많기 때문에, 최적의 bucket size를 확신할 수는 없어서 좋은 방법은 아니라고 보입니다.

다만 시간이 아슬아슬하다 싶을 경우에는 bucket의 사이즈를 고정으로 크게 잡는 것도 나쁘지는 않을 것 같습니다.

또한 이 경우 out_of_bounds 에러가 발생할 수 있으므로 v.size()도 적절히 늘려서 잡아주면 좋습니다.