一个比较常见的技巧–值域分块
link

 #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10, M = 1e5 + 10,MM=350;
int w[N], res[M],res2[M];
int cnt[M],ccnt[MM],sum[MM];
int len;
int n, m;
int ans;
struct node
{
    int id, l, r;
    int a,b;
} que[M];
int read()
{
    char x;
    while ((x = getchar()) > '9' || x < '0')
        ;
    int u = x - '0';
    while ((x = getchar()) <= '9' && x >= '0')
        u = (u << 3) + (u << 1) + x - '0';
    return u;
}
int buf[105];
inline void write(int i)
{
    int p = 0;
    if (i == 0)
        p++;
    else
        while (i)
        {
            buf[p++] = i % 10;
            i /= 10;
        }
    for (int j = p - 1; j >= 0; j--)
        putchar('0' + buf[j]);
}

int get(int x)
{
    return x / len;
}
bool cmp(const node &a, const node &b)
{
    int i = get(a.l), j = get(b.l);
    if (i != j)
        return i < j;
    if (i & 1)
        return a.r < b.r;
    else
        return a.r > b.r;
}
void add(int x, int &res)
{
    cnt[x]++;
    ccnt[get(x)]++;
    if(cnt[x]==1) sum[get(x)]++;
}
void del(int x, int &res)
{
    cnt[x]--;
    ccnt[get(x)]--;
    if(cnt[x]==0) sum[get(x)]--;
}
void cal(int id,int a,int b)
{
    int a1=0,a2=0;
    if(get(a)==get(b))
    {
        for(int i=a;i<=b;i++)
        {
            a1+=cnt[i];
            a2+=(cnt[i]>0);
        }
        res[id]=a1,res2[id]=a2;
        return ;
    }
    int i=a,j=b;
    while(get(i)==get(a))
    {
        a1+=cnt[i];
        a2+=(cnt[i]>0);
        i++;
    }
    while(get(j)==get(b))
    {
        a1+=cnt[j];
        a2+=(cnt[j]>0);
        j--;
    }
    //cout<<i<<" "<<j<<"\n";
    for(int k=get(i);k<=get(j);k++)
    {
        a1+=ccnt[k];
        a2+=sum[k];
    }
    res[id]=a1,res2[id]=a2;
}
int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
        w[i] = read();
    len = max((int)sqrt(double(1ll * n * n) / m), 1);
    for (int i = 1; i <= m; i++)
    {
        que[i].id = i;
        que[i].l = read(), que[i].r = read();
        que[i].a=read(),que[i].b=read();
    }
    sort(que + 1, que + m + 1, cmp);
    for (int k = 1, i = 0, j = 1; k <= m; k++)
    {
        int id = que[k].id, l = que[k].l, r = que[k].r;
        int a=que[k].a,b=que[k].b;
        while (i < r)
            add(w[++i], ans);
        while (i > r)
            del(w[i--], ans);
        while (j < l)
            del(w[j++], ans);
        while (j > l)
            add(w[--j], ans);
        cal(id,a,b);
    }
    for (int i = 1; i <= m; i++)
        cout<<res[i]<<" "<<res2[i]<<"\n";
    return 0;
}