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; }