Rt，分块是自己写的，莫队部分是参照第一篇题解的，但是总是88分

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N=1e5+10;
const int M=sqrt(N)+1;
const int MAXN=5e5+10;
int n,m,t,base[N],L[N],R[N],pos[N];
int B,maxn,bl[MAXN],blv[MAXN],ans[MAXN],res[MAXN],s1[MAXN],s2[MAXN];
unsigned short sum[M][N];
int solve(int l,int r,int a,int b){
	int p=pos[l],q=pos[r],s=0;
	if(p==q){
		for(int i=l;i<=r;i++)
			if(a<=base[i]&&base[i]<=b)
				s++;
		return s;
	}
	for(int i=p+1;i<=q-1;i++)
		s+=(sum[i][b]-sum[i][a-1]);
	for(int i=l;i<=R[p];i++)
		if(a<=base[i]&&base[i]<=b)
				s++;
	for(int i=L[q];i<=r;i++)
		if(a<=base[i]&&base[i]<=b)
			s++;
	return s;
}
struct question{
	int id,l,r,a,b; 
}q[MAXN];
bool cmp(question a,question b){
	return (bl[a.l]^bl[b.l])?bl[a.l]<bl[b.l]:((bl[a.l]&1)?a.r<b.r:a.r>b.r);
}
void del(int p){
	s2[base[p]]--; 
	if(s2[base[p]]<=0)
		s1[blv[base[p]]]--; 
}
void add(int p){
	s2[base[p]]++;
	if(s2[base[p]]<=1)
		s1[blv[base[p]]]++; 
}
int query(int l,int r){
	int ret=0; 
	r=min(r,maxn); 
	if(l>maxn)
		return 0; 
	int ll=blv[l]+1,rr=blv[r]-1;
	if(blv[l]==blv[r]){
		for(int i=l;i<=r;i++)
			ret+=(bool)s2[i];
		return ret; 
	}
	for(int i=ll;i<=rr;i++)
		ret+=s1[i];
	for(int i=l;blv[i]==blv[l]&&l<=maxn;i++)
		ret+=(bool)s2[i];
	for(int i=r;blv[i]==blv[r]&&r>=0;i--)
		ret+=(bool)s2[i];
	return ret;
}
signed main()
{
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout); 
	n=read(),m=read();
	t=sqrt(n);
	B=1.0*n/sqrt(m)+1;
	for(int i=1;i<=n;i++){
		base[i]=read();
		maxn=max(maxn,base[i]),bl[i]=i/B; 
	}
	for(int i=1;i<=t;i++){
		L[i]=(i-1)*t+1;
		R[i]=i*t;
	}
	if(R[t]<n){
		t++;
		L[t]=R[t-1]+1;
		R[t]=n;
	}
	for(int i=1;i<=t;i++){
		for(int j=L[i];j<=R[i];j++)
			pos[j]=i;
		for(int j=L[i];j<=R[i];j++)
			sum[i][base[j]]++;
		for(int j=1;j<=n;j++)
			sum[i][j]=sum[i][j-1]+sum[i][j];
	}
	for(int i=1;i<=m;i++)
		q[i].l=read(),q[i].r=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
	sort(q+1,q+m+1,cmp); 
	int l=1,r=0;
	B=sqrt(maxn)+1; 
	for(int i=0;i<=maxn;i++)
		blv[i]=i/B;
	for(int i=1;i<=m;i++){
		int a=q[i].a,b=q[i].b; 
		while(l<q[i].l)
			del(l++); 
		while(l>q[i].l)
			add(--l); 
		while(r<q[i].r)
			add(++r);
		while(r>q[i].r)
			del(r--);
		res[q[i].id]=solve(q[i].l,q[i].r,a,b);
		ans[q[i].id]=query(a,b); 
	}
	for(int i=1;i<=m;i++) 
		printf("%lld %lld\n",res[i],ans[i]);
	return 0; 
}