수열과 쿼리 1

#include <bits/stdc++.h>

#define MAX_N 100001
#define ll long long
#define all(a) begin(a), end(a)
using namespace std;

ll n, m;
ll A[MAX_N];
vector<ll> seg[MAX_N * 4];
void init(ll u, ll s, ll e) {
    seg[u] = vector<ll>(A + s, A + e + 1);
    sort(all(seg[u]));
    if(s != e) {
        ll m = (s + e) >> 1;
        init(u * 2, s, m);
        init(u * 2 + 1, m + 1, e);
    }
}
ll query(ll u, ll s, ll e, ll l, ll r, ll v) {
    if(r < s or e < l) return 0ll;
    if(l <= s and e <= r) {
        return seg[u].size() - (upper_bound(begin(seg[u]), end(seg[u]), v) - begin(seg[u]));
    }
    ll m = (s + e) >> 1;
    return query(u * 2, s, m, l, r, v) + query(u * 2 + 1, m + 1, e, l, r, v);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(ll i = 1; i <= n; i++) cin>>A[i];
    init(1, 1, n);
    cin>>m;
    for(ll i = 0, s, e, v; i < m; i++) {
        cin>>s>>e>>v;
        cout<<query(1, 1, n, s, e, v)<<'\n';
    }
    return 0;
}