询问非常阴间,有四维限制,但是如果差分一下就可以消去$l1, l2$两维,只有两维限制,可以莫队解决
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e6 + 10;
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
struct QRY {int p1, p2, id, type;} qry[N];
int n, m, cur, cnt1[N], cnt2[N], dat[N], bel[N], L[N], R[N];
long long ans[N];
bool cmp(QRY a, QRY b) {
return bel[a.p1] == bel[b.p1] ? bel[a.p1] & 1 ? a.p2 < b.p2 : a.p2 > b.p2 : a.p1 < b.p1;
}
void init() {
int B = sqrt(n), C = 0;
for (int i = 1; i <= n; i += B) {
L[++C] = i; R[C] = min(i + B - 1, n);
}
for (int i = 1; i <= C; i++) {
for (int j = L[i]; j <= R[i]; j++) bel[j] = i;
}
}
int main() {
n = read(); init();
for (int i = 1; i <= n; i++) dat[i] = read();
m = read();
for (int i = 1; i <= m; i++) {
int l1 = read(), r1 = read(), l2 = read(), r2 = read();
qry[++cur] = (QRY){r1, r2, i, 1}; qry[++cur] = (QRY){l1 - 1, r2, i, 0};
qry[++cur] = (QRY){r1, l2 - 1, i, 0}; qry[++cur] = (QRY){l1 - 1, l2 - 1, i, 1};
}
m = cur; sort(qry + 1, qry + m + 1, cmp);
int p1 = 0, p2 = 0; long long res = 0;
for (int i = 1; i <= m; i++) {
while (p1 < qry[i].p1) p1++, cnt1[dat[p1]]++, res += cnt2[dat[p1]];
while (p1 > qry[i].p1) cnt1[dat[p1]]--, res -= cnt2[dat[p1]], p1--;
while (p2 < qry[i].p2) p2++, cnt2[dat[p2]]++, res += cnt1[dat[p2]];
while (p2 > qry[i].p2) cnt2[dat[p2]]--, res -= cnt1[dat[p2]], p2--;
if (qry[i].type) ans[qry[i].id] += res; else ans[qry[i].id] -= res;
}
for (int i = 1; i <= m >> 2; i++) printf("%d\n", ans[i]);
return 0;
}