solution

发现可以离线。

将所有询问离线下来，按照查询的从小到大排序。并且将数组从小到大排序。按照从小到大的枚举每次询问，同时将所有的数字，将树状数组上位置。然后直接区间查询就行了。

code

/*
* @Author: wxyww
* @Date:   2020-04-29 11:36:43
* @Last Modified time: 2020-04-29 11:41:07
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
#define pi pair<int,int>
pi a[N];
struct node {
    int l,r,x,id;
}Q[N];
bool cmp(const node &A,const node &B) {
    return A.x < B.x;
}
int ans[N],tree[N],n;
void update(int pos,int c) {
    while(pos <= n) {
        tree[pos] += c;
        pos += pos & -pos;
    }
}
int query(int pos) {
    int ret = 0;
    while(pos) {
        ret += tree[pos];
        pos -= pos & -pos;
    }
    return ret;
}
int main() {
    n = read();int m = read();
    for(int i = 1;i <= n;++i) a[i].first = read(),a[i].second = i;
    sort(a + 1,a + n + 1);
    for(int i = 1;i <= m;++i) {
        Q[i].l = read(),Q[i].r = read();Q[i].x = read();
        Q[i].id = i;
    }

    sort(Q + 1,Q + m + 1,cmp);
    int p = 1;

    for(int i = 1;i <= m;++i) {
        while(a[p].first <= Q[i].x && p <= n) {
            update(a[p].second,1);
            ++p;
        } 
        ans[Q[i].id] = query(Q[i].r) - query(Q[i].l - 1);
    }
    for(int i = 1;i <= m;++i) printf("%d\n",ans[i]);


    return 0;
}