考虑到莫队修改次数为 $O(n\sqrt m)$ ，查询次数为 $O(m)$ ，为平衡复杂度，需要使用修改复杂度为 $O(1)$ ，查询复杂度为 $O(\sqrt n)$ 的分块维护当前结果。

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

struct BLOCK {
    int a[N], pos[N];
    int L[400], R[400], cnt[2][400];
    int n, t, len, now;
#define add(x)                           \
    {                                    \
        if (!a[x]) continue;             \
        ans.first += a[x], ans.second++; \
    }

    inline void build(int _n, int _len) {
        n = _n, len = _len;
        while (now + len <= n) L[++t] = now + 1, R[t] = now + len, now += len;
        if (now < n) L[++t] = now + 1, R[t] = n;
        for (int i = 1; i <= t; i++)
            for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
    }

    inline void change(int x, int v) {
        if (v == 1) {
            cnt[0][pos[x]]++, a[x]++;
            if (a[x] == 1) cnt[1][pos[x]]++;
        } else {
            cnt[0][pos[x]]--, a[x]--;
            if (!a[x]) cnt[1][pos[x]]--;
        }
    }

    inline pair<int, int> ask(int l, int r) {
        int bl = pos[l], br = pos[r];
        pair<int, int> ans;
        if (bl == br)
            for (int i = l; i <= r; i++) add(i)
        else {
            for (int i = l; i <= R[bl]; i++) add(i)
            for (int i = L[br]; i <= r; i++) add(i)
            for (int i = bl + 1; i <= br - 1; i++)
                ans.first += cnt[0][i], ans.second += cnt[1][i];
        }
        return ans;
    }
} B;


int n, m, len, a[N];
pair<int, int> ans[1000005];

struct Q {
    int l, r, a, b, x, i;

    inline Q() {}

    inline Q(int l, int r, int a, int b, int i, int len) : l(l), r(r), a(a), b(b), i(i) { x = l / len; }

    inline friend bool operator<(const Q &u, const Q &v) {
        return u.x == v.x ? (u.x & 1) ? u.r < v.r : u.r > v.r : u.x < v.x;
    }
} q[1000005];

int main() {
    scanf("%d%d", &n, &m), B.build(n, (int) sqrt(n));
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    len = max(1, int(n / sqrt(m)));
    for (int i = 1, l, r, a, b; i <= m; i++) {
        scanf("%d%d%d%d", &l, &r, &a, &b);
        q[i] = Q(l, r, a, b, i, len);
    }
    sort(q + 1, q + m + 1);
    for (int i = 1, l = 1, r = 0; i <= m; i++) {
        while (l > q[i].l) B.change(a[--l], 1);
        while (r < q[i].r) B.change(a[++r], 1);
        while (l < q[i].l) B.change(a[l++], -1);
        while (r > q[i].r) B.change(a[r--], -1);
        ans[q[i].i] = B.ask(q[i].a, q[i].b);
    }
    for (int i = 1; i <= m; i++)printf("%d %d\n", ans[i].first, ans[i].second);
    return 0;
}