题目大意：
有 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]&)?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=;
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=;
while(i){
ans+=c[i];
i-=lowbit(i);
}
return ans;
}
void add(int x){
int pos=d[x];
update(pos,);
if(!cnt[pos]) Zupdate(pos,);
cnt[pos]++;
return;
}
void del(int x){
int pos=d[x];
update(pos,-);
cnt[pos]--;
if(!cnt[pos]) Zupdate(pos,-);
return;
}
int main()
{
scanf("%d%d",&n,&m);
block=sqrt(n);
for(int i=;i<=n;i++) {
scanf("%d",&g[i]);
be[i]=(i-)/block+;//分块
f[i]=g[i];
}
for(int i=;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+,A+m+,cmp);
sort(f+,f+n+);
len=unique(f+,f+n+)-f-;
f[len+]=inf;
for(int i=;i<=n;i++) d[i]=lower_bound(f+,f+len+,g[i])-f;// 原数组g[i]中的离散值 d[i]
int l=,r=;
for(int i=;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+,f+len+,A[i].a)-f;
int pos2=lower_bound(f+,f+len+,A[i].b)-f;
if(f[pos2]>A[i].b) pos2--;
s[A[i].id].ans1=query(pos2)-query(pos1-);
s[A[i].id].ans2=Zquery(pos2)-Zquery(pos1-);
}
for(int i=;i<=m;i++) printf("%d %d\n",s[i].ans1,s[i].ans2 );
}