Solution

直接模拟！！别问，问就是模拟，当然模拟的时间复杂度是O(m * n)居然没有超时。。算了先玄学A一发，贴代码。

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == &#39;-&#39;) w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e5 + 7;
int a[N];

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)    a[i] = read();
    while (m--) {
        int l = read(), r = read(), k = read();
        int ans = 0;
        for (int i = l; i <= r; ++i)
            if (a[i] <= k)    ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

哎，别急

这题目不是换个角度思考么，那我们肯定要给题目一点面子，这样简单的模拟，而且极有可能给卡掉的模拟还是要想想正解。没错就是主席树，也就是叫做可持久化线段树的数据结构。
如果懂到这是应该主席树的题目，那么就很简单了，套板子的题目。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == &#39;-&#39;) w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e5 + 7;
int n, m, rt[N], lc[N << 5], rc[N << 5], sum[N << 5], tot;
#define mid (l+r>>1)

void build(int l, int r, int& x, int y, int k) {
    x = ++tot;
    lc[x] = lc[y], rc[x] = rc[y], sum[x] = sum[y] + 1; //先继承父点，再把权值+1
    if (l == r)    return;
    if (k <= mid)    build(l, mid, lc[x], lc[y], k);
    else    build(mid + 1, r, rc[x], rc[y], k);
}

int ask(int l, int r, int x, int y, int ql, int qr) {
    if (l == ql && r == qr)    return sum[y] - sum[x];
    if (qr <= mid)    return ask(l, mid, lc[x], lc[y], ql, qr);
    else if (ql > mid)    return ask(mid + 1, r, rc[x], rc[y], mid + 1, qr);
    else    return ask(l, mid, lc[x], lc[y], ql, mid) + ask(mid + 1, r, rc[x], rc[y], mid + 1, qr);
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        int x = read();
        build(1, 1e5, rt[i], rt[i - 1], x);
    }
    for (int i = 1; i <= m; ++i) {
        int l = read(), r = read(), k = read();
        printf("%d\n", ask(1, 1e5, rt[l - 1], rt[r], 1, k));
    }
    return 0;
}

要吐槽的是主席树200多MS，直接模拟500多MS那我还是模拟把（小声bb） = = ！！

哎，还别……好吧你走吧，离线咱不会 +_+