用的是 莫队+树状数组 的做法。

询问离线下来然后排序，莫队移动指针的同时用两个树状数组记录每个数的出现次数和是否出现，查询直接前缀相减即可。

复杂度是 $O(n\sqrt n\log n)$ .

在 AcWing 上由于复杂度和 $m$ 的范围有 $1e6$ 所以会 TLE . 洛谷 上 $n,m\leq 1e5$ 的范围可过。

//Author: AutomaticUnravelled
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
#define db double
using namespace std;
int read()
{
    int x=0,w=1; char ch=getchar();
    while ( ch>'9' || ch<'0' ) { if ( ch=='-' ) w=-1; ch=getchar(); }
    while ( ch<='9' && ch>='0' ) x=x*10+ch-'0',ch=getchar();
    return x*w;
}

const int N=1e6+10;
int cnt[N],a[N],n,m,bel[N],siz,ans1[N],ans2[N],tl,tr;
struct BIT
{
    #define lowbit(x) ((x)&(-x))
    int tr[N],mx=0;
    void Add( int x,int v ){ x++; for(;x<=mx;x+=lowbit(x)) tr[x]+=v; }
    int Query( int x ) { x++; int res=0;for(;x;x-=lowbit(x))res+=tr[x]; return res; }
}tsum,tnum;
struct Queries
{
    int l,r,a,b,id;
    bool operator < ( Queries &tmp ) { return (bel[l]==bel[tmp.l]) ? r<tmp.r : bel[l]<bel[tmp.l]; }
}q[N];

void Init()
{
    siz=sqrt(n);
    for ( int i=1; i<=n; i++ ) bel[i]=i/siz+1;
}

void Add( int pos )
{
    tsum.Add(a[pos],1);
    if ( cnt[a[pos]]==0 ) tnum.Add(a[pos],1);
    cnt[a[pos]]++;
}

void Del( int pos )
{
    tsum.Add(a[pos],-1);
    if ( cnt[a[pos]]==1 ) tnum.Add(a[pos],-1);
    cnt[a[pos]]--;
}

int main()
{
//freopen( "exam.in","r",stdin );

    n=read(); m=read(); Init();
    for ( int i=1; i<=n; i++ )
        a[i]=read(),tsum.mx=tnum.mx=max(tnum.mx,a[i]+1);
    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+1+m); tl=tr=0; 
    int ql,qr,qa,qb,qi;
    for ( int i=1; i<=m; i++ )
    {
        ql=q[i].l,qr=q[i].r,qa=q[i].a,qb=q[i].b,qi=q[i].id;
        while ( tl<ql ) Del(tl),tl++;
        while ( tl>ql ) tl--,Add(tl);
        while ( tr>qr ) Del(tr),tr--;
        while ( tr<qr ) tr++,Add(tr);
        ans1[qi]=tsum.Query(qb)-tsum.Query(qa-1);
        ans2[qi]=tnum.Query(qb)-tnum.Query(qa-1);
    }

    for ( int i=1; i<=m; i++ ) printf("%d %d\n",ans1[i],ans2[i] );

    return 0;
}