题意：

静态序列 $c_1, \dots, c_n$ ，$m$ 组询问 $(l_i, r_i, a_i, b_i)$ 回答区间 $[l_i, r_i]$ 上值域在 $[a_i, b_i]$ 的数的个数和在值域区间内的数的种类数。

$1 \leq n, m, c_i \leq 10^5$ 。

题解：

莫队查询，变成维护值域上的单点插入区间查询。

用值域分块来维护，根号平衡。

复杂度 $\mathcal{O}(n \sqrt m + m \sqrt n)$ 。

pair<int,int> operator - (const pair<int,int> lhs, const pair<int,int> rhs) {
    return {lhs.first - rhs.first, lhs.second - rhs.second};
}
struct block {
#define gb(x) ((x)/bs)
#define hob(x) ((x)*bs)
#define eob(x) min(n,((x)+1)*bs-1)
    int n, bs;
    vector<int> cnt, tag, tag2;
    void init(int _n) {
        n = _n;
        bs = sqrt(n);
        cnt.resize(n + 1), tag.resize(gb(n) + 1);
        tag2.resize(gb(n) + 1);
    }
    void insert(int x, int c) {
        tag2[gb(x)] -= cnt[x] > 0;
        cnt[x] += c;
        tag[gb(x)] += c;
        tag2[gb(x)] += cnt[x] > 0;
    }
    pair<int,int> _qry(int x) {
        int ret1 = 0, ret2 = 0;
        int b = gb(x);
        rep(i,0,b - 1) ret1 += tag[i], ret2 += tag2[i];
        rep(i,hob(b),x) ret1 += cnt[i], ret2 += cnt[i] > 0;
        return {ret1, ret2};
    }
    pair<int,int> qry(int l, int r) {
        return _qry(r) - (l == 1 ? make_pair(0, 0) : _qry(l - 1));
    }
} bloc;
vector<int> a, belong;
vector< pair<int,int> > ans;
struct ask { int l, r, a, b, id; };
inline bool mocmp(const ask& x, const ask& y) {
    return belong[x.l] ^ belong[y.l] ? belong[x.l] < belong[y.l] : belong[y.l] ? x.r < y.r : x.r > y.r;
}
vector< ask > as;
inline void add(int x) { return bloc.insert(a[x], 1); }
inline void del(int x) { return bloc.insert(a[x], -1); }
signed main() {
   int n = read(), m = read(), _n = 0;
    a.resize(n + 1), belong.resize(n + 1);
    as.resize(m); ans.resize(m);
    rep(i,1,n) a[i] = read(), _n = max(a[i], _n);
    int mbs = max(1, (int)(n / sqrt(m * 2.0 / 3)));
    rep(i,1,n) belong[i] = (i - 1) / mbs + 1;
    rep(i,0,m - 1) {
        as[i].l = read(), as[i].r = read(), as[i].a = read(), as[i].b = read();
        as[i].id = i;
    }
    sort(as.begin(), as.end(), mocmp);
    bloc.init(_n);
    int l = 1, r = 0;
    for(ask &cur : as) {
        // expend first, delete second.
        while(r < cur.r) add(++ r);
        while(l > cur.l) add(-- l);
        while(r > cur.r) del(r --);
        while(l < cur.l) del(l ++);
        ans[cur.id] = bloc.qry(cur.a, cur.b);
    }
    for(auto x : ans) printf("%d %d\n", x.first, x.second);
    return 0;
}