rt,原题数据放过 $O(nm)$ 的暴力就挺离谱的。

加几组 hack 数据，存放在本题的附件中，也可以直接去提交测试。

generator:

#include<iostream>
#include<cstdlib>
using namespace std;
const int N=1e5;
int main(){
	freopen("hack4.in","w",stdout);
	cout<<N<<" "<<N<<endl;
	for(int i=1;i<=N;i++){
		int t=rand();
		if(t<0) t=-t;
		t%=N;
		t+=1;
		cout<<t<<" ";
	}
	cout<<endl;
	for(int i=1;i<=N;i++){
		int sb=rand();
		if(sb<0) sb=-sb;
		sb%=114;
		cout<<1+sb<<" "<<N-sb<<" "<<1+sb<<" "<<N-sb<<endl;
	}
	return 0;
}

std:

#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int N=1e5+10;
struct node{
	int l,r;
}bl[N],bl1[N];
struct sb{
	int l,r,aa,bb,ln,fm,ans1,ans2;
}ask[N];
bool cmp1(sb pre,sb nxt){
	if(pre.ln!=nxt.ln) return pre.ln<nxt.ln;
	else return pre.r<nxt.r;
}
bool cmp2(sb pre,sb nxt){
	return pre.fm<nxt.fm;
}
int a[N];
int vst[N],zyh[N],sum[N],blo[N];
int n,m,len,len1,tt,cnt,cnt1;
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	len=sqrt(n);
	len1=sqrt(N-10);
	for(int i=1;i<=n;i+=len){
		cnt++;
		bl[cnt].l=i;
		bl[cnt].r=min(n,i+len-1);
	}
	for(int i=1;i<=N-10;i+=len1){
		cnt1++;
		bl1[cnt1].l=i;
		bl1[cnt1].r=min(N-10,i+len1-1);
	}
	for(int i=1;i<=m;i++){
		cin>>ask[i].l>>ask[i].r>>ask[i].aa>>ask[i].bb;
		ask[i].fm=i;
		for(int j=1;j<=cnt;j++){
			if(bl[j].l<=ask[i].l&&ask[i].l<=bl[j].r){
				ask[i].ln=j;
				break;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=cnt1;j++){
			if(bl1[j].l<=a[i]&&a[i]<=bl1[j].r){
				blo[i]=j;
				break;
			}
		}
	}
	sort(ask+1,ask+m+1,cmp1);
	int ll=1,rr=1;
	vst[a[1]]++;
	zyh[blo[1]]++;
	sum[blo[1]]++;
	for(int i=1;i<=m;i++){
		while(ask[i].l<ll){
			ll--;
			if(vst[a[ll]]==0) sum[blo[ll]]++;
			vst[a[ll]]++;
			zyh[blo[ll]]++;
		}
		while(rr<ask[i].r){
			rr++;
			if(vst[a[rr]]==0) sum[blo[rr]]++;
			vst[a[rr]]++;
			zyh[blo[rr]]++;
		}
		while(ll<ask[i].l){
			if(vst[a[ll]]==1) sum[blo[ll]]--;
			vst[a[ll]]--;
			zyh[blo[ll]]--;
			ll++;
		}
		while(ask[i].r<rr){
			if(vst[a[rr]]==1) sum[blo[rr]]--;
			vst[a[rr]]--;
			zyh[blo[rr]]--;
			rr--;
		}
		int ql=0,qr=0;
		for(int j=1;j<=cnt1;j++){
			if(bl1[j].l<=ask[i].aa){
				ql=j;
			}
		}
		for(int j=1;j<=cnt1;j++){
			if(ask[i].bb<=bl1[j].r){
				qr=j;
				break;
			}
		}
		int tmp1=0,tmp2=0;
		if(ql==qr){
			for(int j=ask[i].aa;j<=ask[i].bb;j++){
				tmp1+=vst[j];
				if(vst[j]) tmp2++;
			}
			ask[i].ans1=tmp1;
			ask[i].ans2=tmp2;
			continue;
		}
		for(int j=ask[i].aa;j<=bl1[ql].r;j++){
			tmp1+=vst[j];
			if(vst[j]) tmp2++;
		}
		for(int j=bl1[qr].l;j<=ask[i].bb;j++){
			tmp1+=vst[j];
			if(vst[j]) tmp2++;
		}
		for(int j=ql+1;j<=qr-1;j++){
			tmp1+=zyh[j];
			tmp2+=sum[j];
		}
		ask[i].ans1=tmp1;
		ask[i].ans2=tmp2;
	}
	sort(ask+1,ask+m+1,cmp2);
	for(int i=1;i<=m;i++){
		cout<<ask[i].ans1<<" "<<ask[i].ans2<<'\n';
	}
	return 0;
}