[SNOI2017]一个简单的询问

深碍√TFBOYSˉ_ 2023-10-11 11:16 44阅读 0赞

[题目][Link 1]

写水题快乐一下

显然\\(\\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 <bits/stdc++.h>
    #define re register
    #define LL long long
    inline 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;
    }

转载于:https://www.cnblogs.com/asuldb/p/11351891.html

[Link 1]: https://www.luogu.org/problem/P5268