rt，本题为莫队板题，但是不会只好写CDQ，已计算过大小大概在30MB左右但还是爆了前3个点

代码在这里

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5;
constexpr int MAXM = 1e6;

namespace Otakus
{
    struct BinaryIndexTree
    {
        int c[MAXN + 10];

        void add(int x, int o)
        {
            while (x <= MAXN)
                c[x] += o, x += x & -x;
        }

        int qry(int x)
        {
            int res = 0;
            while (x)
                res += c[x], x -= x & -x;
            return res;
        }

        int qry(int l, int r)
        {
            if (l > r)
                return 0;
            return qry(r) - qry(l - 1);
        }
    };

    using bit = BinaryIndexTree;

    int n, m;
    int A[MAXM + 10], B[MAXM + 10], ans[MAXM + 10], l[MAXM + 10], r[MAXM + 10];

    struct Ele
    {
        int pre;
        int val;
    } e[MAXN + 10];

    bool cmp(Ele x, Ele y) { return x.pre < y.pre; }

    namespace CDQ
    {
        struct Qry
        {
            int id;
            bool opt;
        } q[MAXM * 2];

        bool cmpr(Qry x, Qry y)
        {
            int xr = x.opt ? r[x.id] : l[x.id];
            int yr = y.opt ? r[y.id] : l[y.id];
            if (xr != yr)
                return xr < yr;
            return l[x.id] < l[y.id];
        }

        bool cmpl(Qry x, Qry y)
        {
            return l[x.id] < l[y.id];
        }

        void CDQ(int L, int R, int LL, int RR, bit &cnt)
        {
            if (LL > RR || L > R)
                return;
            if (L == R)
            {
                int w, id;
                for (int i = LL; i <= RR; i++)
                {
                    w = q[i].opt ? 1 : -1;
                    id = q[i].id;
                    ans[id] += w * (e[L].val >= A[id] && e[L].val <= B[id] && e[L].pre <= l[id]);
                }
                return;
            }

            int res = -1;
            int i = LL, j = RR, mid = (L + R) / 2;
            int md, qr;
            while (i <= j)
            {
                md = (i + j) / 2;
                qr = q[md].opt ? r[q[md].id] : l[q[md].id];
                if (qr <= mid)
                    res = md, i = md + 1;
                else
                    j = md - 1;
            }

            if (res == -1)
                CDQ(mid + 1, R, LL, RR, cnt);
            else
            {
                CDQ(L, mid, LL, res, cnt);
                CDQ(mid + 1, R, res + 1, RR, cnt);
            }

            sort(e + L, e + mid + 1, cmp);
            if (res + 1 <= RR)
                sort(q + res + 1, q + RR + 1, cmpl);

            i = L;
            if (res == -1)
                j = LL;
            else
                j = res + 1;
            int w, id;
            while (j <= RR)
            {
                while (i <= mid && e[i].pre <= l[q[j].id])
                    cnt.add(e[i].val, 1), i++;
                w = q[j].opt ? 1 : -1;
                id = q[j].id;
                ans[id] += w * cnt.qry(A[id], B[id]);
                j++;
            }

            for (int s = L; s < i; s++)
                cnt.add(e[s].val, -1);
        }
        void solve()
        {
            for (int i = 1; i <= m; i++)
            {
                cin >> l[i] >> r[i] >> A[i] >> B[i];
                l[i] -= 1;
                q[i * 2 - 1].id = q[i * 2].id = i;
                q[i * 2 - 1].opt = 1;
                q[i * 2].opt = 0;
            }

            sort(q + 1, q + 2 * m + 1, cmpr);

            bit cnt;

            for (int i = 1; i <= 2 * m; i++)
            {
                int qr = q[i].opt ? r[q[i].id] : l[q[i].id];
                if (qr > 0)
                {
                    CDQ(1, n, i, 2 * m, cnt);
                    break;
                }
            }
        }

    } // namespace CDQ

    void init()
    {
        cin >> n >> m;
        int *pr = new int[MAXN + 10];
        for (int i = 1; i <= MAXN; i++)
            pr[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> e[i].val;
            e[i].pre = pr[e[i].val];
            pr[e[i].val] = i;
        }

        delete[] pr;
        pr = nullptr;

        CDQ::solve();

        for (int i = 1; i <= m; i++)
            cout << ans[i] << '\n';
    }

} // namespace Otakus

int main()
{
    // sro CDQ orz
    Otakus::init();
    return 0;
}