///直接我们开一个pair然后存每个数 每个数的下标,
///然后把M次查询的按照K升序排序一次,pair按照序列升序排序,
///然后就是利用树状数组来搞,离线做,我们只需要比较一次序列和K的大小就可以,
///因为我们是利用树状数组来做,那么[l,r]的区间答案,我们是不是可以直接[1,r]-[1,l-1]这样直接求出来。
///因为我们的K是排序了,然后每次处理的K都是由小的开始比较 ,所以后面的K可以直接使用之前区间的比较的每个dou[].
#include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define debug(x) cout << #x << ": " << x << endl; #define debug1(x) cout<<"xxx"<<endl; #define ll long long #define ull unsigned long long #pragma GCC optimize("Ofast","inline","-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #define mse(a,b) memset(a,b,sizeof a); using namespace std; const int maxx=1e6+100; const int mod=1e9+7; struct node { int l,r,x,id; bool operator <(const node &a) { return x<a.x; } }; node q[maxx]; pair<int,int>a[maxx]; int n,m; int dou[maxx]; int oo[maxx]; int lowbit(int x) { return x&(-x); } void update(int x) { while(x<=n) { oo[x]++; x+=lowbit(x); } } int query(int x) { int res=0; while(x>0) { // cout<<123<<endl; res+=oo[x]; x-=lowbit(x); } return res; } int main() { fio; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i ++) scanf("%d",&a[i].first),a[i].second = i; sort(a + 1,a + 1 + n);///按照值的大小排序 for(int i = 1;i <= m;i ++)///保存询问 并且保留下标 { scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x); q[i].id = i; } sort(q + 1, q + m + 1);///按照值排序 int k = 1; for(int i = 1;i <= m;i ++) { while(a[k].first <= q[i].x && k <= n)///当前值小于查询的值就更新 { update(a[k].second);///用该数在数组中位置维护 k ++ ; } dou[q[i].id] = query(q[i].r) - query(q[i].l - 1);///区间查询 } for(int i = 1;i <= m;i ++)///离线回答 printf("%d\n",dou[i]); return 0; } /* 5 3 1 2 3 4 5 1 3 5 1 3 5 1 3 5 */