【题解】

首先就普通莫队来维护每个块中出现的数的个数和出现的数的值的个数，再用一个数组统计区间内每个数出现的次数，就行了，$O(\sqrt{n})$每次询问，那么总复杂度$O(m\sqrt{n})$，正好够。

# include <stdio.h>
# include <math.h> 
# include <algorithm>
using namespace std;
int n,m,t,left=1,right;
int a[100010],cnt[100010],w[100010];
int f[10010],g[10010];
int a1[1000010],a2[1000010];


struct quest {
	int l,r,a,b,id;
	bool operator <(const quest &A) const{
		if (w[l]==w[A.l]) return r<A.r;
		else return l<A.l;
	}
}q[1000010];

inline void xy(int l,int r,int id) {
	if(w[l]==w[r]) {
		for (int i=l;i<=r;++i) if(cnt[i]) a1[id]+=cnt[i],a2[id]++;
	} else {
		for (int i=w[l]*t-1;i>=l;--i) if(cnt[i]) a1[id]+=cnt[i],a2[id]++;
		for (int i=w[r]*t-t;i<=r;++i) if(cnt[i]) a1[id]+=cnt[i],a2[id]++; 
		for (int i=w[l]+1;i<w[r];++i) a1[id]+=f[i],a2[id]+=g[i];
	}
}

inline void u(int x) {
	++f[w[x]];++cnt[x];
	if(cnt[x]==1) g[w[x]]++;
}

inline void v(int x) {
	--f[w[x]];--cnt[x];
	if(cnt[x]==0) g[w[x]]--;
}

int main() {
	scanf("%d%d",&n,&m);
	t=sqrt(n/2);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]),w[i]=i/t+1;
	for (int i=1;i<=m;++i) scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b),q[i].id=i;
	sort(q+1,q+m+1);
	for (int i=1;i<=m;++i) {
		while(right<q[i].r) u(a[++right]);
		while(left<q[i].l) v(a[left++]);
		while(right>q[i].r) v(a[right--]);
		while(left>q[i].l) u(a[--left]);		
		xy(q[i].a,q[i].b,q[i].id); 
	}
	for (int i=1;i<=m;++i) printf("%d %d\n",a1[i],a2[i]);
}