题解跑了74ms我的三秒多，但我实在找不出来哪里挂了TAT……

#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;

int n,m,a[200010],len,bl[200010],len2,manx;
int cnt[200010],cnt2[200010],cnt3[200010],l=1,r,bel[200010];
pair<int,int> ans[200010];
struct ques
{
	int l,r,x,y,i;
}b[200010];
bool cmp(ques x,ques y)
{
	if(bl[x.l]!=bl[y.l]) return x.l<y.l;
	if(bl[x.l]%2) return x.r<y.r;
	return x.r>y.r;
}
void ad(int x)
{
	cnt[x]++;cnt2[bel[x]]++;
	if(cnt[x]==1) cnt3[bel[x]]++;
}
void del(int x)
{
	cnt[x]--;cnt2[bel[x]]--;
	if(!cnt[x]) cnt3[bel[x]]--;
}
pair<int,int> query(int x,int y)
{
	int res1=0,res2=0;
	if(bel[y]-bel[x]<=1)
	{
		for(int i=x;i<=y;i++)
		{
			res1+=cnt[i];
			if(cnt[i]) res2++;
		}
	}
	else
	{
		for(int i=x;i<=bel[x]*len2;i++)
		{
			res1+=cnt[i];
			if(cnt[i]) res2++;
		}
		for(int i=(bel[y]-1)*len2+1;i<=y;i++)
		{
			res1+=cnt[i];
			if(cnt[i]) res2++;
		}
		for(int i=bel[x]+1;i<=bel[y]-1;i++)
		{
			res1+=cnt2[i];res2+=cnt3[i];
		}
	}
	return make_pair(res1,res2);
}
signed main()
{
//	freopen("P4396_1.in","r",stdin);
//	freopen("tanglong.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;len=1.0*n/sqrt(m)+1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];bl[i]=(i-1)/len+1;manx=max(manx,a[i]);
	}
	len2=sqrt(manx)+1;
	for(int i=1;i<=manx;i++) bel[i]=(i-1)/len2+1;
	for(int i=1;i<=m;i++)
	{
		cin>>b[i].l>>b[i].r>>b[i].x>>b[i].y;b[i].i=i;
	}
	sort(b+1,b+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		while(l>b[i].l) ad(a[--l]);
		while(r<b[i].r) ad(a[++r]);
		while(l<b[i].l) del(a[l++]);
		while(r>b[i].r) del(a[r--]);
		ans[b[i].i]=query(b[i].x,b[i].y);
	}
	for(int i=1;i<=m;i++) cout<<ans[i].first<<' '<<ans[i].second<<'\n';
	system("pause");
	return 0;
}