思路：
莫队+树状数组维护；
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 100005 struct QueryType {
int l,r,a,b,id;
};
struct QueryType qu[maxn*]; int n,sum[maxn],sum_[maxn],ti[maxn],ans[maxn*][];
int ai[maxn],size,bel[maxn],m; inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
} inline int lowbit(int x)
{
return x&(-x);
} inline void sadd(int x,int k)
{
while(x<=n) sum[x]+=k,x+=lowbit(x);
} inline int ssum(int p,int x)
{
int res=;p--;
while(x) res+=sum[x],x-=lowbit(x);
while(p) res-=sum[p],p-=lowbit(p);
return res;
} inline void tadd(int x,int k)
{
while(x<=n) sum_[x]+=k,x+=lowbit(x);
} inline int tsum(int p,int x)
{
int res=;p--;
while(x) res+=sum_[x],x-=lowbit(x);
while(p) res-=sum_[p],p-=lowbit(p);
return res;
} inline bool cmp(QueryType aaa,QueryType bbb)
{
if(bel[aaa.l]==bel[bbb.l])
{
if(bel[aaa.r]==bel[bbb.r])
{
if(aaa.l==bbb.l) return aaa.r<bbb.r;
else return aaa.l<bbb.l;
}
return bel[aaa.r]<bel[bbb.r];
}
else return bel[aaa.l]<bel[bbb.l];
} inline void updata(int now,int x)
{
int pre=ti[now];
ti[now]+=x,sadd(now,x);
if(pre==&&ti[now]==) tadd(now,);
if(pre==&&ti[now]==) tadd(now,-);
} int main()
{
in(n),in(m),size=sqrt(n);for(int i=;i<=n;i++) in(ai[i]),bel[i]=(i-)/size;
for(int i=;i<=m;i++) in(qu[i].l),in(qu[i].r),in(qu[i].a),in(qu[i].b),qu[i].id=i;
sort(qu+,qu+m+,cmp);int l=,r=,pos;
for(int no=;no<=m;no++)
{
if(l<qu[no].l) for(int i=l;i<qu[no].l;i++) updata(ai[i],-);
else for(int i=l-;i>=qu[no].l;i--) updata(ai[i],);
if(r>qu[no].r) for(int i=r;i>qu[no].r;i--) updata(ai[i],-);
else for(int i=r+;i<=qu[no].r;i++) updata(ai[i],);
l=qu[no].l,r=qu[no].r,ans[qu[no].id][]=ssum(qu[no].a,qu[no].b),ans[qu[no].id][]=tsum(qu[no].a,qu[no].b);
}
for(int i=;i<=m;i++) printf("%d %d\n",ans[i][],ans[i][]);
return ;
}