BOJ 13537 수열과 쿼리 1

📝 문제 정보

링크: https://www.acmicpc.net/problem/13537

🧐 관찰 및 접근

부분수열에서 물어보는 쿼리가 있으니, 세그먼트 트리가 먼저 생각이 난다.
- 그런데 쿼리가 좀 까다롭다.
이럴때, $N, M$모두 10만이므로 제곱근 분할법을 한번 생각해보자.
수가 $C$개 들어있는 버킷을 $B$개 만든다면 $(C = N/B$), 버킷 내의 수들을 정렬하는데 $O(B \times C\log{C})$, 버킷들에 대해 답을 구하는데에 $O(B \times \log{C})$
따라서 이들을 최소화하기 위해서는 적당히 $\sqrt{N}$보다 약간 크게 잡으면 될 것 같다.

💻 풀이

코드 (C++):

const int sq = 700;
struct sqrtDecomposition{
    int N;
    vector<int> A;
    vector<vector<int>> bucket;

    sqrtDecomposition(int N, vector<int> &A): N(N), A(A){
        bucket.resize((N-1)/sq+1);
        rep(i, 0, N) bucket[i/sq].push_back(A[i]);
        for(int i = 0; i < (int)bucket.size(); i++) sort(all(bucket[i]));
    };

    int query(int L, int R, int val){
        int ret = 0;
        for(int i = L; i <= R;){
            if(i%sq == 0 && i+sq-1 <= R){
                ret += bucket[i/sq].end() - upper_bound(all(bucket[i/sq]), val);
                i += sq;
            }
            else{
                ret += A[i] > val;
                i++;
            }
        }
        return ret;
    }
};

void solve(){
    int N; cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    sqrtDecomposition sd(N, A);
    int Q; cin >> Q;
    while(Q--){
        int i, j, k; cin >> i >> j >> k;
        cout << sd.query(i-1, j-1, k) << "\n";
    }
}