BOJ 13537 수열과 쿼리 1

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