后续。

不想写主席树怎么办，这里给一个好写的分块。

考虑离散化之后对值域进行分块。然后每个块里存放对应的数。因为查询的是 $>k$，所以整块 $>k$ 的可以直接在里面二分左右端点加贡献，部分大于 $k$ 的最多只有一个块，块内二分一下暴力查，最多枚举的数的数量等于块长。即可做到 $O(n\sqrt{n}\log n)$，常数较小。

因为枚举的 $\sqrt{n}$ 是不带 $\log$ 的，因此还可以再调块长平衡复杂度到 $O(n\sqrt{n\log n})$。

由于本题数据太水了（也可能是出题人根本就想不到会有神人这样做），实测直接对值而不是排名分块都能过。下面是这种写法的代码，其实可以随便叉。

#include<bits/stdc++.h>
using namespace std;
int n, q, m, a[100005], kc, ks, kl[2005], kr[2005], bel[100005];
vector<int> buk[2005], vec;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        vec.emplace_back(a[i]); 
    }
    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    m = vec.size();
    kc = sqrt(m);
    ks = (m + kc - 1) / kc;
    for (int i = 1; i <= ks; i++){
        kl[i] = kr[i - 1] + 1;
        kr[i] = kl[i] + kc - 1;
    }
    kr[ks] = m;
    for (int i = 1; i <= ks; i++)
        for (int j = kl[i]; j <= kr[i]; j++)
            bel[j] = i;
    for (int i = 1; i <= n; i++){
        a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
        buk[bel[a[i]]].emplace_back(i);
    }
    cin >> q;
    while (q--){
        int l, r, k;
        cin >> l >> r >> k;
        k = upper_bound(vec.begin(), vec.end(), k) - vec.begin();
        int ans = 0;
        for (int j = bel[k] + 1; j <= ks; j++){
            auto pl = lower_bound(buk[j].begin(), buk[j].end(), l);
            auto pr = upper_bound(buk[j].begin(), buk[j].end(), r) - 1;
            ans += pr - pl + 1;
        }
        int u = bel[k];
        auto pl = lower_bound(buk[u].begin(), buk[u].end(), l);
        while (pl != buk[u].end() && *pl <= r){
            ans += (a[*pl] > k);
            ++pl;
        }
        cout << ans << "\n";
    }
    return 0;
}