LYDSY 2038

题目大意

暂无

题目解法

暂无

RTFC

#include <algorithm>
#include <cstdio>
int C[50050], bSize, res;
template <typename T>
T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
struct query
{
    int l, r, id;
} Q[50050];
inline bool operator<(const query &lhs, const query &rhs) { return lhs.l / bSize == rhs.l / bSize ? lhs.r < rhs.r : lhs.l / bSize < rhs.l / bSize; }
int ans[50050][2], cnt[50050];
inline void ins(int x)
{
    res -= cnt[x] * cnt[x];
    cnt[x]++;
    res += cnt[x] * cnt[x];
}
inline void del(int x)
{
    res -= cnt[x] * cnt[x];
    cnt[x]--;
    res += cnt[x] * cnt[x];
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    while (bSize * bSize < n) bSize++;
    for (int i = 1; i <= n; i++) scanf("%d", C + i);
    for (int i = 0; i < m; i++) scanf("%d%d", &Q[i].l, &Q[i].r), Q[i].id = i;
    std::sort(Q, Q + m);
    for (int i = 0, L = 1, R = 0; i < m; i++)
        if (Q[i].l == Q[i].r)
            ans[Q[i].id][0] = 0, ans[Q[i].id][1] = 1;
        else
        {
            while (L < Q[i].l) del(C[L]), L++;
            while (R < Q[i].r) R++, ins(C[R]);
            while (L > Q[i].l) L--, ins(C[L]);
            while (R > Q[i].r) del(C[R]), R--;
            int range = Q[i].r - Q[i].l + 1;
            long long a = res - range, b = 1ll * range * (range - 1), c = gcd(a, b);
            ans[Q[i].id][0] = int(a / c), ans[Q[i].id][1] = int(b / c);
        }
    for (int i = 0; i < m; i++) printf("%d/%d\n", ans[i][0], ans[i][1]);
    return 0;
}