rt，TLE了一个测试点。

思路是常规的莫队和值域分块。

//
//  Created by mori on 2023/08/22 上午10:24 星期二
//
//  P4867 Gty的二逼妹子序列 on Luogu 
//  Coded with CLion
//  

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)

template <typename T>
void ckmin (T &_0, T _1) { if (_1 < _0) _0 = _1; }

template <typename T>
void ckmax (T &_0, T _1) { if (_1 > _0) _0 = _1; }

int read () {
    int res = 0;
    bool f = false;
    char temp = getchar();
    for (; !isdigit(temp); temp = getchar()) f = temp == '-';
    for (; isdigit(temp); temp = getchar()) res = res * 10 + temp - '0';
    if (f) return -res;
    return res;
}

char gc () {
    char temp = getchar();
    while (temp == '\n' || temp == '\r' || temp == ' ') temp = getchar();
    return temp;
}

constexpr int maxn = 1e5 + 5, maxm = 1e6 + 5;
int n, m, bl[maxn], len, a[maxn], ans[maxm], sum[1000], vis[maxn], len2, bl2[maxn];

struct Q {
    int l, r, id, al, ar;
} q[maxm];

inline void add (int x) {
    sum[bl2[x]] += !vis[x]++;
}

inline void del (int x) {
    sum[bl2[x]] -= !--vis[x];
}

int query (int l, int r) {
    int lid = bl2[l], rid = bl2[r], res = 0;
    if (lid == rid) {
        rep (i, l, r) if (vis[i]) ++res;
    } else {
        for (int i = l; bl2[i] == lid; i++) if (vis[i]) ++res;
        for (int i = r; bl2[i] == rid; --i) if (vis[i]) ++res;
        rep (i, lid + 1, rid - 1) res += sum[i];
    }
    return res;
}

signed main () {
    n = read(), m = read();

    len = pow(n * n / m, 0.5), len2 = sqrt(n);
    rep (i, 1, n) a[i] = read(), bl[i] = i / len, bl2[i] = (i - 1) / len2 + 1;

    rep (i, 1, m) {
        q[i].l = read(), q[i].r = read();
        q[i].al = read(), q[i].ar = read();
        q[i].id = i;
    }

    sort(q + 1, q + 1 + n, [&] (const Q &q1, const Q &q2) {
        return bl[q1.l] ^ bl[q2.l] ? q1.l < q2.l : bl[q1.l] & 1 ? q1.r < q2.r : q1.r > q2.r;
    });

    int l = 1, r = 0;
    rep (i, 1, m) {
        const auto ul = q[i].l, ur = q[i].r;
        while (l > ul) add(a[--l]);
        while (r < ur) add(a[++r]);
        while (l < ul) del(a[l++]);
        while (r > ur) del(a[r--]);
        ans[q[i].id] = query(q[i].al, q[i].ar);
    }

    rep (i, 1, m) printf("%d\n", ans[i]);
    return 0;
}