RE on #4,#7,#8.

WA on #6,#9~12.

Code:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000000 + 10;
int n, m, len, num;
int a[maxn], belong[maxn];
int st[maxn], ed[maxn];
int cnt[maxn];
pair<int, int> info[maxn];
struct query
{
    int l, r, a, b, id;
    bool operator<(const query &x) const
    {
        if (l / len != x.l / len)
            return l < x.l;
        if ((l / len) & 1)
            return r < x.r;
        return r > x.r;
    }
} q[maxn];
pair<int, int> ans[maxn];

void init_blocks()
{
    len = 1.0 * n / sqrt(m), num = n / len;
    for (int i = 1; i <= num; i++)
        st[i] = len * (i - 1) + 1, ed[i] = len * i;
    ed[num] = n;
    for (int i = 1; i <= num; i++)
        for (int j = st[i]; j <= ed[i]; j++)
            belong[j] = i;
}

inline void add(int val)
{
    info[belong[val]].first++;
    if (++cnt[val] == 1)
        info[belong[val]].second++;
}
inline void del(int val)
{
    info[belong[val]].first--;
    if (--cnt[val] == 0)
        info[belong[val]].second--;
}

pair<int, int> query(int l, int r)
{
    pair<int, int> res;
    int L = belong[l], R = belong[r];
    if (L == R)
    {
        for (int i = l; i <= r; i++)
            res.first += cnt[i], res.second += (bool)cnt[i];
        return res;
    }
    for (int i = l; i <= ed[L]; i++)
        res.first += cnt[i], res.second += (bool)cnt[i];
    for (int i = st[R]; i <= r; i++)
        res.first += cnt[i], res.second += (bool)cnt[i];
    for (int i = L + 1; i < R; i++)
        res.first += info[i].first, res.second += info[i].second;
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    init_blocks();
    int cntq = 0, cntm = 0;
    for (int i = 1; i <= m; i++)
    {
        cin >> q[i].l >> q[i].r >> q[i].a >> q[i].b;
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);
    int L = 1, R = 0;
    for (int i = 1; i <= m; i++)
    {
        while (L < q[i].l)
            del(a[L++]);
        while (L > q[i].l)
            add(a[--L]);
        while (R < q[i].r)
            add(a[++R]);
        while (R > q[i].r)
            del(a[R--]);
        ans[q[i].id] = query(q[i].a, q[i].b);
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i].first << ' ' << ans[i].second << endl;
    return 0;
}