【题意概述】
给定一个长度为n的序列和若干个询问，每次询问序列的区间[L,R]中，大于等于a且小于等于b的数的个数，以及大于等于a且小于等于b的数值的个数。
序列长度不超过10^5，询问次数不超过10^6.
【题解】
使用莫队算法。与BZOJ 3809非常相似，只是比那道题多了一种询问，即求出区间[L,R]中大于等于a且小于等于b的数的个数。显然这个用树状数组维护即可。
那么本题维护两个树状数组即可。
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N (100010)
#define M (1000010)
#define rg register
#define lowbit (x&-x)
using namespace std;
int n,m,cnt[N],a[N],t1[N],t2[N],bl[N],ans[2][M];
struct queue{
int l,r,a,b,pos;
}q[M];
inline int read(){
int k=0,f=1; char c=getchar();
while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
return k*f;
}
inline bool cmp(queue a,queue b){
if(bl[a.l]==bl[b.l]){
if(bl[a.l]&1) return a.r<b.r;
return a.r>b.r;
}
return bl[a.l]<bl[b.l];
}
inline void add1(int x,int del){for(;x<=n;x+=lowbit) t1[x]+=del;}
inline void add2(int x,int del){for(;x<=n;x+=lowbit) t2[x]+=del;}
inline int query1(int x){
int ret=0;
for(;x;x-=lowbit) ret+=t1[x];
return ret;
}
inline int query2(int x){
int ret=0;
for(;x;x-=lowbit) ret+=t2[x];
return ret;
}
inline void move(int pos,int del){
if(del==1){
if(!cnt[a[pos]]) add2(a[pos],1);
add1(a[pos],1);
cnt[a[pos]]++;
}
else{
cnt[a[pos]]--;
if(!cnt[a[pos]]) add2(a[pos],-1);
add1(a[pos],-1);
}
}
int main(){
n=read(); m=read();
int block=sqrt(n);
for(rg int i=1;i<=n;i++) a[i]=read(),bl[i]=(i-1)/block+1;
for(rg int i=1;i<=m;i++){
q[i].l=read(); q[i].r=read();
q[i].a=read(); q[i].b=read();
q[i].pos=i;
}
sort(q+1,q+1+m,cmp);
for(rg int i=1,l=1,r=0;i<=m;i++){
while(l<q[i].l) move(l++,-1);
while(l>q[i].l) move(--l,1);
while(r<q[i].r) move(++r,1);
while(r>q[i].r) move(r--,-1);
ans[0][q[i].pos]=query1(q[i].b)-query1(q[i].a-1);
ans[1][q[i].pos]=query2(q[i].b)-query2(q[i].a-1);
}
for(rg int i=1;i<=m;i++) printf("%d %d
",ans[0][i],ans[1][i]);
return 0;
}