洛谷P5268 [SNOI2017]一个简单的询问

询问非常阴间，有四维限制，但是如果差分一下就可以消去$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;
}