「題解」洛谷 P1494 [國家集訓隊]小Z的襪子

題目

P1494 [國家集訓隊]小Z的襪子

思路

\(ans = \sum_{i = 1}^{n} p_i\)，\(p_i\) 是拿到兩根顔色為 \(i\) 的襪子的機率。

\(p_i = \dfrac{s_i \times (s_i - 1)}{len\times (len - 1)}\)，\(s_i\) 是顔色 \(i\) 在區間中出現的次數，\(len\) 是區間長度。

用莫隊維護出現次數，分子很容易算，分母是固定的，約分一下。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define M 50001

typedef long long ll;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll now, fz[M], fm[M];
int n, m, sqrn, a[M], num[M], cnt[M];
struct query {
    int x, y, len, id;
    friend bool operator < (query q1, query q2) {
        if (num[q1.x] == num[q2.x]) return q1.y < q2.y;
        return num[q1.x] < num[q2.x];
    }
}q[M];

void add(int x) {
    int temp = cnt[x]; ++cnt[x];
    now = now - 1ll * temp * (temp - 1) + 1ll * temp * cnt[x];
}

void del(int x) {
    int temp = cnt[x]; --cnt[x];
    now = now - 1ll * temp * (temp - 1) + 1ll * cnt[x] * (cnt[x] - 1);
}

int main() {
    scanf("%d %d", &n, &m), sqrn = n / sqrt(m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        num[i] = (i - 1) / sqrn + 1;
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &q[i].x, &q[i].y);
        q[i].id = i, q[i].len = q[i].y - q[i].x + 1;
    }
    std::sort(q + 1, q + m + 1);
    int l = 1, r = 1; cnt[a[1]] = 1;
    for (int i = 1; i <= m; ++i) {
    	while (l > q[i].x) add(a[--l]);
        while (r < q[i].y) add(a[++r]);
        while (l < q[i].x) del(a[l++]);
        while (r > q[i].y) del(a[r--]);
        if (now == 0) fz[q[i].id] = 0, fm[q[i].id] = 1;
        else {
            ll g = gcd(now, 1ll * q[i].len * (q[i].len - 1));
            fz[q[i].id] = now / g, fm[q[i].id] = 1ll * q[i].len * (q[i].len - 1) / g;
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (fz[i] == 0) fm[i] = 1;
        printf("%lld/%lld\n", fz[i], fm[i]);
    }
    return 0;
}