https://ac.nowcoder.com/acm/problem/19427
题意：给出1e5个值为[1,1e5]的数组，查询1e5次[l,r]区间中的小于x(<=1e5)的数 的个数，1<=l<=r<=1e5。
思路：暴力必死
(1)树状数组+离线处理
所有数都是小于1e5，可以开一个树状数组c统计，对原数组离线处理，从小到大插入树状数组，对查询也离线处理，从小到大查询，对于每一个查询的x，将小于x的原数组元素先插入，后统计。由于都是从小到大，不会计算重复。时间复杂度O(m*logn)，空间消耗较大。
(2)莫队裸题
(3)数据扩展
- 将数据上限全部都增加到1e6，莫队超时，树状数组还是稳如老狗
- 只将x增加到1e9甚至1e18，数组大小会爆，不能用树状数组，只能用莫队
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #define ll long long #define inf 0x3f3f3f3f///负无穷小 -0x7f using namespace std; int n,m; struct node { int a; int idx; }; node arr[100005]; struct query { int l; int r; int x; int idx; int ans; }; query q[100005]; int c[100005];///树状数组 bool cmp1(node p1,node p2)///对原数组插入顺序做出调整 { if(p1.a==p2.a) return p1.idx<p2.idx; return p1.a<p2.a; } bool cmp2(query q1,query q2)///查询离线处理，同步树状数组求和 { return q1.x<q2.x; } bool cmp3(query q1,query q2)///按顺序输出答案 { return q1.idx<q2.idx; } int lowbit(int x) { return x&(-x); } void add(int x,int val)///在x的位置添加val值 { while(x<=n+1) { c[x]+=val; x+=lowbit(x); } } int sum(int x)///求前x的前缀和 { int res=0; while(x>0) { res+=c[x]; x-=lowbit(x); } return res; } int main()///NC19427离线+树状数组 { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&arr[i].a); arr[i].idx=i; } for(int i=1;i<=m;i++) { scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x); q[i].idx=i; } sort(arr+1,arr+n+1,cmp1); sort(q+1,q+m+1,cmp2); int i=1,j=1; for(i=1;i<=m;i++) { for(;j<=n && arr[j].a<=q[i].x;j++)///把原数组中小于 查询的x 的插入树状数组 add(arr[j].idx,1); q[i].ans=sum(q[i].r)-sum(q[i].l-1); } sort(q+1,q+m+1,cmp3); for(int i=1;i<=m;i++) printf("%d ",q[i].ans); }