题目大意：
有 n 个整数组成的数组，m 次询问，每次询问中有四个参数 l ，r，a，b 。问你在[l，r] 的区间内的所有数中，值属于[a，b] 的数的个数以及种类数。
分析：
1、由于可以离线操作，故采用莫队。
2、由于在莫队的基础上还涉及区间[a，b]的值的个数，故可以用前缀和的思想，求得出sum(b) - sum(a - 1)即可。由于与莫队使用是动态的，故需要用树状数组维护，因为可以 logn 动态插入。
3、对于求区间种类数，需要用第二个树状数组维护。且需要用 cnt[] 数组来标记当前数是否是第一次出现或最后一次出现的数。如果是第一次出现且需 add，则更新当前点以及后置点 + +（树状数组插入）；若为最后一次出现且需 del，则更新当前点以及后置点 - - 即可。
4、由于数组中数的范围未给定，在树状数组中可能爆空间，故需要离散化。
算法正确性：
树状数组的原理在于，若当前点值为 x ，则对于所有>= x 的数，都要加上这个数的贡献，即 + + 。比如有 >= x 的数 y ，在求前缀和（即在求 <= y 的数的个数）时，所有出现过的且 <= y 的值的点 x ，都在之前的插入对答案做有贡献。可想而知，树状数组的这种优点导致可以存储前缀和。
然后再注意一下离散化的细节即可，最好在去重的末端加入一个极大值，这样lower_bound 就不会越界，且在求 pos1 以及 pos2 时能很好地判断取值。
然后莫队排序时，需要用到奇偶排序，不然会 T 一个点。
代码如下：
#include<iostream> #include<algorithm> #include<string.h> #include<cmath> using namespace std; #define inf 0x3f3f3f3f #define maxn 100008 int n,m,block,len; int be[maxn]; int g[maxn],f[maxn],d[maxn]; int c[maxn],z[maxn],cnt[maxn]; struct S{ int ans1,ans2; }s[maxn]; struct Mo{ int id; int l,r; int a,b; }A[maxn]; bool cmp(Mo q,Mo w){ return (be[q.l]^be[w.l])?q.l<w.l:(be[q.l]&1)?q.r<w.r:q.r>w.r; //奇偶排序 } inline int lowbit(int x){return x&(-x);} void Zupdate(int i,int q){ while(i<=len){ z[i]+=q; i+=lowbit(i); } return; } int Zquery(int i){ int ans=0; while(i){ ans+=z[i]; i-=lowbit(i); } return ans; } void update(int i,int q){ while(i<=len){ c[i]+=q; i+=lowbit(i); } return; } inline int query(int i){ int ans=0; while(i){ ans+=c[i]; i-=lowbit(i); } return ans; } void add(int x){ int pos=d[x]; update(pos,1); if(!cnt[pos]) Zupdate(pos,1); cnt[pos]++; return; } void del(int x){ int pos=d[x]; update(pos,-1); cnt[pos]--; if(!cnt[pos]) Zupdate(pos,-1); return; } int main() { scanf("%d%d",&n,&m); block=sqrt(n); for(int i=1;i<=n;i++) { scanf("%d",&g[i]); be[i]=(i-1)/block+1;//分块 f[i]=g[i]; } for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&A[i].l,&A[i].r,&A[i].a,&A[i].b); A[i].id=i; } sort(A+1,A+m+1,cmp); sort(f+1,f+n+1); len=unique(f+1,f+n+1)-f-1; f[len+1]=inf; for(int i=1;i<=n;i++) d[i]=lower_bound(f+1,f+len+1,g[i])-f;// 原数组g[i]中的离散值 d[i] int l=1,r=0; for(int i=1;i<=m;i++){ while(l<A[i].l) del(l++); while(l>A[i].l) add(--l); while(r<A[i].r) add(++r); while(r>A[i].r) del(r--); int pos1=lower_bound(f+1,f+len+1,A[i].a)-f; int pos2=lower_bound(f+1,f+len+1,A[i].b)-f; if(f[pos2]>A[i].b) pos2--; s[A[i].id].ans1=query(pos2)-query(pos1-1); s[A[i].id].ans2=Zquery(pos2)-Zquery(pos1-1); } for(int i=1;i<=m;i++) printf("%d %d ",s[i].ans1,s[i].ans2 ); }