BOJ 14504 수열과 쿼리 18

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);
        }
    }
}