BOJ 14504 수열과 쿼리 18

📝 문제 정보

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

🧐 관찰 및 접근

수열과 쿼리 1과 비슷한데, 업데이트 쿼리가 추가되었다.
- 같은 방법으로 풀되, 배열 정렬 말고 multiset으로 관리하면 되지 않을까?
- 헉, multiset에서 거리를 계산할때 쓰는 distance함수가 $O(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]));
    };

    void update(int i, int val){
        int b = i/sq;
        auto it = lower_bound(all(bucket[b]), A[i]);
        *it = val;
        A[i] = val;
        sort(all(bucket[b]));
    }

    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 op; cin >> op;
        if(op == 1){
            int i, j, k; cin >> i >> j >> k;
            cout << sd.query(i-1, j-1, k) << "\n";
        }
        else{
            int i, k; cin >> i >> k;
            sd.update(i-1, k);
        }
    }
}