这里提供一个无脑分块做法。

看到数据范围 $5\times 10^4$，考虑分块，设块长为 $\sqrt n$。令 $sum_{i,j}$ 表示前 $j$ 个数对第 $i$ 个块产生的贡献。这个东西可以 $O(n\sqrt n)$ 预处理出来。

对于每个询问，把它拆成三个部分：

• 区间二的所有整块 对 整个区间一 产生的贡献
• 区间一的所有整块 对 区间二的散块 产生的贡献
• 区间一的散块 对 区间二的散块 产生的贡献

建议自己画个图理解一下。

前两个部分显然可以直接利用 $sum$ 来搞，对于第三个部分，暴力开桶，扫一遍就没了。

时空复杂度均为 $O(n\sqrt n)$。常数较莫队略大，但不卡常也能做到稳定跑过。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50005, maxb = 255;
int n, m, block, t;
int a[maxn], ind[maxn];
int sum[maxb][maxn];
int st[maxb], ed[maxb], pos[maxn];
int cnt[maxn];
void discrete() {
    memcpy(ind, a, sizeof(a)); sort(ind + 1, ind + 1 + n);
    int len = unique(ind + 1, ind + 1 + n) - ind - 1;
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(ind + 1, ind + 1 + n, a[i]) - ind;
}
void getsum(int k) {
    for (int i = st[k]; i <= ed[k]; i++) cnt[a[i]]++;
    for (int i = 1; i <= n; i++) sum[k][i] = sum[k][i - 1] + cnt[a[i]];
    for (int i = st[k]; i <= ed[k]; i++) cnt[a[i]]--;
}
void init() {
    block = sqrt(n); t = ceil(n * 1. / block);
    for (int i = 1; i <= t; i++) {
        st[i] = (i - 1) * block + 1; ed[i] = min(i * block, n);
        for (int j = st[i]; j <= ed[i]; j++) pos[j] = i;
    }
    for (int i = 1; i <= t; i++) getsum(i);
}
int query(int l1, int r1, int l2, int r2) {
    int p1 = pos[l1], q1 = pos[r1], p2 = pos[l2], q2 = pos[r2], ans = 0;
    for (int i = p2 + 1; i <= q2 - 1; i++) ans += sum[i][r1] - sum[i][l1 - 1];
    for (int i = p1 + 1; i <= q1 - 1; i++)
        if (p2 != q2) ans += sum[i][ed[p2]] - sum[i][l2 - 1] + sum[i][r2] - sum[i][st[q2] - 1];
        else ans += sum[i][r2] - sum[i][l2 - 1];
    if (p2 == q2)
        for (int i = l2; i <= r2; i++) cnt[a[i]]++;
    else {
        for (int i = l2; i <= ed[p2]; i++) cnt[a[i]]++;
        for (int i = st[q2]; i <= r2; i++) cnt[a[i]]++;
    }
    if (p1 == q1)
        for (int i = l1; i <= r1; i++) ans += cnt[a[i]];
    else {
        for (int i = l1; i <= ed[p1]; i++) ans += cnt[a[i]];
        for (int i = st[q1]; i <= r1; i++) ans += cnt[a[i]];
    }
    if (p2 == q2)
        for (int i = l2; i <= r2; i++) cnt[a[i]]--;
    else {
        for (int i = l2; i <= ed[p2]; i++) cnt[a[i]]--;
        for (int i = st[q2]; i <= r2; i++) cnt[a[i]]--;
    }
    return ans;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    discrete();
    init();
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
        cout << query(l1, r1, l2, r2) << endl;
    }
    return 0;
}