수열과 쿼리 18 [BOJ 14504]

수열과 쿼리 3 문제는 머지 소트 트리를 이용해 해결할 수 있다. 아직 안 풀어봤다면 수열과 쿼리 3을 꼭 먼저 풀고, 수열과 쿼리 18에서 업데이트 쿼리를 어떻게 적용할 수 있을지 생각해보자. 여담으로, 이 문제는 수열과 쿼리 1.5와 완전히 같은 문제이다.

 

문제 요약

길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 수행한다.

1 i j k : 구간 [i, j]에서 A의 원소 중 k보다 큰 것의 개수를 출력

2 i k : A[i]=k로 업데이트

 

사용 알고리즘

제곱근 분할법

 

풀이

k보다 큰 원소의 수를 lower_bound나 upper_bound를 이용하여 구하겠다는 발상까지는 머지 소트 트리와 같다. 하지만 업데이트 쿼리가 들어온다면 기존의 머지 소트 트리에서 O(logN)개의 정렬된 vector를 관리해야하는데, vector는 원소를 중간에 삽입할 수 없기에 매번 O(NlogN)의 sort를 해주어야하고, 시간제한 안에 들어오는 풀이를 만들 수 없다. set을 사용한다면 정렬된 수들의 집합을 관리할 수는 있겠지만 set의 iterator 간에는 빼기 연산이 적용되지 않기에 쿼리를 제대로 처리할 수 없다. 따라서 무언가 다른 방법을 생각해야한다.

위 관찰에서 vector의 원소를 정렬된 상태로 관리하기 위해서는 O(NlogN)의 시간이 필요하다는 것을 발견했으므로, 전체 구간을 저장하는 vector는 무용지물이라는 것을 알게되었다. 즉, vector를 트리 형식으로 관리하는 것은 의미가 없게 되었으므로, 자연스럽게 수열을 분할하여 저장한다는 생각을 할 수 있다. 그렇다면 분할된 수열의 길이 중 가장 큰 수를 P라고 했을때 O(PlogP)의 시간복잡도에 업데이트 쿼리를 처리할 수 있다. 그렇다면 수열의 개수는 N/P개 이상일 것이고, 출력 쿼리에서 N/P개 이상의 vector를 확인해야 하므로 O((N/P)logP)의 시간복잡도에 출력 쿼리를 처리할 수 있다. 이렇게 되면 두 시간복잡도가 최대한 비슷할 때 전체 시간복잡도가 최적이 됨을 알 수 있고, 이 때의 P=sqrt(N)이 된다. 이렇게 수열을 sqrtN개로 분할하여 적당한 작업을 수행하는 것을 제곱근 분할법, 영어로는 Squareroot Decompostion이라고 한다. 더 낮은 티어의 Mo's Algorithm에서 이미 익숙해진 방법이지만, 상위 티어로 갈수록 제곱근 분할법은 시간복잡도에 sqrtN이 붙는 문제들의 중심 테크닉으로 사용되기도 한다.

 

이제 수열을 sqrtN의 길이의 버켓 sqrtN개로 나누어주었다고 하자. N이 제곱수가 아니어도 대충 sqrtN 정도 스케일의 숫자를 사용하면 된다.

상대적으로 쉬운 2번 쿼리부터 보자. A[i]를 k로 바꾸는 업데이트 쿼리이므로, i가 속하는 버켓을 찾는다. 먼저 버켓의 원소들 중 기존 A[i]인 수를 하나 찾아 k로 바꾼 후, 버켓을 정렬한다. 다음 업데이트를 위해 A[i]=k를 저장해놓는 것도 잊지 말자. 시간복잡도 O(sqrtNlogN)에 처리된다.

1번 쿼리는 구간이기 때문에 여러 개의 구간을 관리해야할 수도 있다.

① i, j가 같은 버켓에 속하는 경우

구간 [i, j]의 길이가 sqrtN보다 작다. 그러니 모든 원소를 확인해 k보다 큰 것의 개수를 세도 O(sqrtN)에 쿼리를 처리할 수 있다.

② i, j가 다른 버켓에 속하는 경우

구간 [i, j]를 버켓 단위로 쪼개면, 3가지 영역으로 나눌 수 있다.

- 가장 처음, 시작하는 부분 : 버켓 하나의 일부가 포함된다. (붉은색 부분)

- 가장 마지막, 끝나는 부분 : 버켓 하나의 일부가 포함된다. (푸른색 부분)

- 그 외 중간 부분 : 버켓 여러 개의 전체가 포함된다. (보라색 부분)

붉은색 부분과 푸른색 부분은 i, j가 같은 버켓에 속하는 경우처럼 모든 원소를 확인해주면 된다. O(sqrtN)에 처리된다.

보라색 부분에서 하나의 버켓에 대해서는 O(logN)에 upper_bound를 이용하여 k보다 큰 원소의 수를 셀 수 있다. 이 과정을 최대 O(sqrtN)개의 버켓에 대해 반복하므로 시간복잡도 O(sqrtNlogN)에 처리된다.

 

따라서 모든 쿼리를 처리하는 시간복잡도는 O(MsqrtNlogN)이다. 하지만 출력 쿼리의 보라색 부분에서 O(sqrtN)개의 부분을 모두 사용하는 경우는 많지 않고, 그 외 상수도 작아 같은 시간복잡도를 가진 다른 문제의 코드들보다는 훨씬 빠른 시간에 돌아간다. 구현도 어렵지 않으니 직접 해보는 것을 추천한다.

 

코드

#include <bits/stdc++.h>
#define SIZE 100010
using namespace std;
int N,M,A[SIZE],c;
vector<int>v[320];
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>N;
    for(int i=1;i<=N;i++)cin>>A[i];
    int sqrtN=sqrt(N),tc,l,r,k;
    for(int i=1;i<=N;i++){
        if(i%sqrtN==0)c++;
        v[c].push_back(A[i]);
    }
    for(int i=0;i<=c;i++)sort(v[i].begin(),v[i].end());
    for(cin>>M;M--;){
        cin>>tc>>l>>r;
        if(tc&1){
            int ret=0;
            cin>>k;
            if(l/sqrtN==r/sqrtN){
                for(int i=l;i<=r;i++)if(A[i]>k)ret++;
            }
            else{
                for(int i=l;i<sqrtN*(l/sqrtN+1);i++)if(A[i]>k)ret++; //빨간색 부분
                for(int i=sqrtN*(r/sqrtN);i<=r;i++)if(A[i]>k)ret++; //파란색 부분
                for(int i=l/sqrtN+1;i<r/sqrtN;i++)ret+=v[i].end()-upper_bound(v[i].begin(),v[i].end(),k); //보라색 부분
            }
            printf("%d\n",ret);
        }
        else{
            for(int i=0;i<v[l/sqrtN].size();i++)if(v[l/sqrtN][i]==A[l]){
                v[l/sqrtN][i]=r;
                break;
            }
            A[l]=r;
            sort(v[l/sqrtN].begin(),v[l/sqrtN].end());
        }
    }
}

 

https://unorderedmap.tistory.com/13

1일 1수쿼 기록장