记录编号	616716	评测结果	AAAAAAAAAT
题目名称	1822.[AHOI 2013] 作业	最终得分	90
用户昵称	2_16鸡扒拌面	是否通过	未通过
代码语言	C++	运行时间	2.885 s
提交时间	2026-06-30 11:20:19	内存使用	4.95 MiB

/*莫队算法为什么是神？在谈论这个问题之前，我想先说说其他数据结构算法相较于莫队究竟差在了哪里。
首先是犯下傲慢之罪的 ST 表，搞个 O(1) 查询算法名称就使用“神通”的词汇，这种傲慢的不支持修改算法注定走不长远。事实也是如此，在靠着时间复杂度赢了莫队之后一直在走下坡路，最终泯然众人。与之相比莫队就很谦卑，O(n23?)，带修 O(n35?) 都是莫队留给稀疏表的慈悲，莫队不是不会 O(logn)，只是不想通过太强悍的算法速度让稀疏表绝望所以故意不用。可笑有些人不理解莫队的良苦用心，竟然还用这些事讥讽莫队，我劝你们，耗子尾汁。
然后是犯下愤怒之罪的树状数组，因为一个点单点修改就找人家 logn 个祖宗谈话，区间问题有人提到莫队就怒气冲冲地炫耀时间复杂度的小常数，违背了莫队在 OI Wiki 中的一句话：“普通莫队是不能带修改的。”于是莫队降下了他的惩罚，树状数组悲惨失宠，在之后的区间问题中被线段树抢走职务，维护失败，一蹶不振。
接着是犯下懒惰之罪的线段树，自以为泛用就了不起了，自创区间打懒标记，另外大家有所不知，n 个数建立线段树，tr1? 闭上眼睛憧憬未来的时候，其脑海中看见的画面，正是站在区间查询之中的莫队，那时莫队告诉他：“你只可到这里，不可越过。”（指部分问题一般线段树不好处理）然而，莫队的劝说不但没有让线段树迷途知返，竟然还敢伙同愤怒的树状数组搞树套树，于是莫队降下了他的惩罚，吉司机线段树的下限变成了 log2n，时间复杂度惨遭毒瘤清算，从此从单 logn 算法之位坠落，永世不得翻身。
再然后是犯下了嫉妒之罪的回滚莫队，屡次被莫队击败，但口服心不服的回滚莫队暗中嫉妒着莫队，甚至胆敢当中说出如果没有普通莫队的话，大家都会回滚莫队了这种话。于是，在含金量最高的卡常大赛上，回滚莫队被莫队正面击溃。不过，念在回滚莫队最终怂了莫队的淫威，并且践行莫队的意志讨伐了屡次以下犯上的数据结构后，莫队应许了他在算法界的一切.
还有犯下贪婪之罪的主席树。只是算法的基础，主席树便拥有 n 个版本，而这，自然是因为莫队的应允。莫队允许主席树带线段树擅自出走，以 O(logn) 另立中央，只为让主席树代替自己争取更优的复杂度，甚至自己在复杂度“故意”输给 ST 表，将一切荣耀都归于他。但最后主席树却被胜利蒙蔽了双眼，也不再聆听莫队的教诲，甚至自以为荣光已经超过了莫队，竟允许自己的部下树套树自诩“他们才是好用的算法”，用这种算法亵渎莫队的尊严。于是莫队降下了惩罚，主席树此后在卡空间中被狂暴鸿儒，而线段树趁机背刺，树状数组带走了他的常数，各个版本提桶跑路，最后落得孤独终老的下场。
之后便是犯下暴食之罪的树套树。在主席树堕落之后，莫队开始寻找下一个代言人。这一次，他选中了树套树。相较于莫队，树套树无疑是不完美的。他没有莫队足以维护任何问题的合并，也没有足够的空间，甚至会导向出题人认定的坏算法。莫队认为或许是自己给主席树的压力过大，于是这一次莫队放任树套树开大空间，最终，树套树成功了。然而，完工后的树套树不但自诩“好用的算法”，更妄图染指莫队的威严，最终他也因此犯下了暴食之罪。空间开成了大卫带。
最后，犯下淫欲之罪的哈希表。耗尽了 O(n) 的时限后，莫队已经相当虚弱了。出题人用数据范围吸走了莫队的时间，莫队已经无力再惩罚年轻人。可此刻已经决心优化的莫队在最后依然心系数据结构的未来，于是他选中了第三位代言人――方便快速的哈希表。作为第三任代言人，哈希表很好的处理了区间问题，但在配合算法上，哈希表挡不住异端的诱惑，被 log 算法直接牛走，吸走了莫队赋予自己的时间复杂度，在最后站错了队，最后被莫队橄榄，彻底身败名裂。
至此，莫队终于将胆敢冒犯他的威严的算法斩杀殆尽，因此不出所料，在算法大赛的最终战，被单调队列以及单调栈踹上了 5×106 只脚，永世跑不完代码，可谓可喜可贺，万众欢呼。*/
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=100010;
const int B=316;

int n,m,bs;
int a[N],cnt[N],bc[N/B+5],bk[N/B+5];

struct Q{int l,r,a,b,id;}q[N];
pair<int,int> ans[N];

int vb(int x){return (x-1)/B+1;}

void add(int p){
    int v=a[p], id=vb(v);
    if(!cnt[v]++)bk[id]++;
    bc[id]++;
}

void del(int p){
    int v=a[p], id=vb(v);
    if(!--cnt[v])bk[id]--;
    bc[id]--;
}

pair<int,int> ask(int lo,int hi){
    int num=0,kind=0,bl=vb(lo),br=vb(hi);
    if(bl==br){
        for(int i=lo;i<=hi;i++){
            if(cnt[i])
            {
                num+=cnt[i];
                kind++;
            }
        }
        return {num,kind};
    }
    for(int i=lo;i<=bl*B;i++)
    {
        if(cnt[i])
        {
            num+=cnt[i];
            kind++;
        }
    }
    for(int i=bl+1;i<br;i++)
    {
        num+=bc[i];
        kind+=bk[i];
    }
    for(int i=(br-1)*B+1;i<=hi;i++)
    {
        if(cnt[i])
        {
            num+=cnt[i];
            kind++;
        }
    }
    return {num,kind};
}

int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
    return x*f;
}

int main()
{
    //freopen("ahoi2013_homework.in","r",stdin);
    //freopen("ahoi2013_homework.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    bs=max(1,(int)(n/sqrt(m)));
    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+m+1,[](Q&x,Q&y)
    {
        int xb=x.l/bs,yb=y.l/bs;
        if(xb!=yb)return xb<yb;
        return xb&1?x.r>y.r:x.r<y.r;
    });
    int L=1,R=0;
    for(int i=1;i<=m;i++)
    {
        while(L>q[i].l) add(--L);
        while(R<q[i].r) add(++R);
        while(L<q[i].l) del(L++);
        while(R>q[i].r) del(R--);
        ans[q[i].id]=ask(q[i].a,q[i].b);
    }
    for(int i=1;i<=m;i++) printf("%d %d\n",ans[i].fi,ans[i].se);
    return 0;
}