写水题快乐一下

显然\(\operatorname{get(l_1,r_1,x)}\times \operatorname{get(l_2,r_2,x)}\)可以拆成

\(\operatorname{pre(r_1,x)}\times \operatorname{pre(r_2,x)}+\operatorname{pre(l_1-1,x)}\times \operatorname{pre(l_2-1,x)}\)减去\(\operatorname{pre(r_1,x)}\times \operatorname{pre(l_2-1,x)}+\operatorname{pre(r_2,x)}\times \operatorname{pre(l_1-1,x)}\)

\(\operatorname{pre(i,x)}\)表示\([1,i]\)中\(x\)出现次数

显然我们把一个询问拆成四个，\(\operatorname{pre(l,x)}\times \operatorname{pre(r,x)}\)变成一组询问\(l,r\)即可，直接大力莫队莽

代码

#include 
    
     #define re register#define LL long longinline int read() {    char c = getchar();    int x = 0;    while (c < '0' || c > '9') c = getchar();    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - 48, c = getchar();    return x;}int a[50005], tax[50005], tmp[50005];struct Ask {    int l, r, o, rk;} q[200005];int n, m, Q, sz;LL ans, Ans[50005];inline int cmp(const Ask &A, const Ask &B) {    if (A.l / sz == B.l / sz)        return A.r < B.r;    return A.l < B.l;}inline void del(int x, int o) {    ans -= 1ll * tax[a[x]] * tmp[a[x]];    tmp[a[x]] += o;    ans += 1ll * tax[a[x]] * tmp[a[x]];}inline void add(int x, int o) {    ans -= 1ll * tax[a[x]] * tmp[a[x]];    tax[a[x]] += o;    ans += 1ll * tax[a[x]] * tmp[a[x]];}int main() {    n = read();    for (re int i = 1; i <= n; i++) a[i] = read();    Q = read();    for (re int l1, l2, r1, r2, i = 1; i <= Q; i++) {        l1 = read(), r1 = read(), l2 = read(), r2 = read();        q[++m] = (Ask){ r1, r2, 1, i };        if (l1 > 1 && l2 > 1)            q[++m] = (Ask){ l1 - 1, l2 - 1, 1, i };        if (l2 > 1)            q[++m] = (Ask){ r1, l2 - 1, -1, i };        if (l1 > 1)            q[++m] = (Ask){ r2, l1 - 1, -1, i };    }    for (re int i = 1; i <= m; i++)        if (q[i].l > q[i].r)            std::swap(q[i].l, q[i].r);    sz = n / (std::sqrt(m)) + 1;    std::sort(q + 1, q + m + 1, cmp);    for (re int l = 0, r = 0, i = 1; i <= m; i++) {        while (r < q[i].r) add(++r, 1);        while (l > q[i].l) del(l--, -1);        while (l < q[i].l) del(++l, 1);        while (r > q[i].r) add(r--, -1);        Ans[q[i].rk] += 1ll * q[i].o * ans;    }    for (re int i = 1; i <= Q; i++) printf("%lld\n", Ans[i]);    return 0;}