记录编号	617139	评测结果	AAAAAAWWWT
题目名称	1822.[AHOI 2013] 作业	最终得分	60
用户昵称	2_16鸡扒拌面	是否通过	未通过
代码语言	C++	运行时间	3.465 s
提交时间	2026-07-04 10:11:51	内存使用	8.91 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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

const int N = 1e5 + 10;
const int MQ = 1e6 + 10;
const int MB = 256; // 2^8
const int BUF_SIZE = 1 << 20;

// 缓冲区
char buf_in[BUF_SIZE], *p1 = buf_in, *p2 = buf_in;
char buf_out[BUF_SIZE], *p_out = buf_out;

inline char gc() {
    if(p1 == p2) {
        p2 = (p1 = buf_in) + fread(buf_in, 1, BUF_SIZE, stdin);
        if(p1 == p2) return EOF;
    }
    return *p1++;
}

inline int read() {
    int x = 0;
    char c = gc();
    while(c < '0' || c > '9') c = gc();
    while(c >= '0' && c <= '9') {
        x = x * 10 + (c ^ 48);
        c = gc();
    }
    return x;
}

inline void write(int x) {
    static char stk[12];
    register int top = 0;
    if(!x) *p_out++ = '0';
    else {
        while(x) {
            stk[++top] = (x % 10) ^ 48;
            x /= 10;
        }
        while(top) *p_out++ = stk[top--];
    }
}

int n, m, B;
int a[N];
int ql[MQ], qr[MQ], qa[MQ], qb[MQ], blk[MQ], order[MQ];
int ans1[MQ], ans2[MQ];

// 值域分块
int t, L[MB], R[MB], bl[N], s1[MB], s2[MB], cnt[N];

void build() {
    register int i;
    t = (100000 >> 8);
    for(i = 1; i <= t; i++) {
        L[i] = ((i - 1) << 8) + 1;
        R[i] = i << 8;
    }
    R[t] = 100000;
    for(i = 1; i <= 100000; i++)
        bl[i] = i >> 8;
}

inline void add(int x) {
    register int b = bl[x];
    if(!cnt[x]++) s1[b]++;
    s2[b]++;
}

inline void del(int x) {
    register int b = bl[x];
    --cnt[x];
    --s2[b];
    if(!cnt[x]) --s1[b];
}

inline int ask1(int l, int r) {
    register int p = bl[l], q = bl[r];
    register int ans = 0, i;
    if(p == q) {
        for(i = l; i <= r; ++i) ans += (cnt[i] > 0);
        return ans;
    }
    for(i = l; i <= R[p]; ++i) ans += (cnt[i] > 0);
    for(i = L[q]; i <= r; ++i) ans += (cnt[i] > 0);
    for(i = p + 1; i < q; ++i) ans += s1[i];
    return ans;
}

inline int ask2(int l, int r) {
    register int p = bl[l], q = bl[r];
    register int ans = 0, i;
    if(p == q) {
        for(i = l; i <= r; ++i) ans += cnt[i];
        return ans;
    }
    for(i = l; i <= R[p]; ++i) ans += cnt[i];
    for(i = L[q]; i <= r; ++i) ans += cnt[i];
    for(i = p + 1; i < q; ++i) ans += s2[i];
    return ans;
}

int main() {
    freopen("ahoi2013_homework.in", "r", stdin);
    freopen("ahoi2013_homework.out", "w", stdout);
    
    n = read(); m = read();
    B = max(1, (int)(n / sqrt(m) * 0.85));
    
    register int i;
    for(i = 1; i <= n; ++i) a[i] = read();
    for(i = 1; i <= m; ++i) {
        ql[i] = read(); qr[i] = read();
        qa[i] = read(); qb[i] = read();
        order[i] = i;
        blk[i] = ql[i] / B;
    }
    
    sort(order + 1, order + m + 1, [](int i, int j) {
        if(blk[i] != blk[j]) return blk[i] < blk[j];
        return (blk[i] & 1) ? (qr[i] < qr[j]) : (qr[i] > qr[j]);
    });
    
    build();
    
    register int l = 1, r = 0, idx;
    for(i = 1; i <= m; ++i) {
        idx = order[i];
        while(l > ql[idx]) add(a[--l]);
        while(r < qr[idx]) add(a[++r]);
        while(l < ql[idx]) del(a[l++]);
        while(r > qr[idx]) del(a[r--]);
        ans1[idx] = ask1(qa[idx], qb[idx]);
        ans2[idx] = ask2(qa[idx], qb[idx]);
    }
    
    for(i = 1; i <= m; ++i) {
        write(ans2[i]);
        *p_out++ = ' ';
        write(ans1[i]);
        *p_out++ = '\n';
    }
    
    fwrite(buf_out, 1, p_out - buf_out, stdout);
    return 0;
}