洛谷 P1494 [国家集训队]小Z的袜子

题意简述

一些袜子排成一排，每个袜子有固定的颜色。
每次询问在[l,r]的袜子中等概率选两只，求有多大的概率抽到两只一样颜色的。

题解思路

维护一个计数数组cnt[i]表示当前[l,r]区间颜色为i的袜子有几只。
转移的时候如果加入元素x,那么cnt[x]变成cnt[x]+1,对答案的贡献为2cnt[x]+1

代码

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
struct Q{
    int l, r, i;
    ll len;
}b[50010];
int n, m, len, lal, lar;
int a[50010], bnum[50010], cnt[50010];
ll s;
ll ans[50010][2];
bool cmp(Q x, Q y)
{
    return bnum[x.l] == bnum[y.l] ? bnum[x.r] < bnum[y.r] : bnum[x.l] < bnum[y.l];
}
void add(int x)
{
    s += (cnt[x] << 1) | 1;
    ++cnt[x];
}
void del(int x)
{
    s -= (cnt[x] << 1) - 1;
    --cnt[x];
}
int main()
{
    scanf("%d%d", &n, &m);
    len = sqrt(n);
    for (register int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (register int i = 1; i <= n; ++i)
        bnum[i] = (i - 1) / len + 1;
    for (register int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &b[i].l, &b[i].r);
        b[i].i = i;
        b[i].len = b[i].r - b[i].l + 1;
    }
    sort(b + 1, b + m + 1, cmp);
    for (register int i = b[1].l; i <= b[1].r; ++i)
        add(a[i]);
    if (s != b[1].len)
    {
        ll x1 = s - b[1].len, x2 = b[1].len * (b[1].len - 1);
        ll g = __gcd(x1, x2);
        ans[b[1].i][0] = x1 / g;
        ans[b[1].i][1] = x2 / g;
    }
    else ans[b[1].i][1] = 1;
    lal = b[1].l;
    lar = b[1].r;
    for (register int i = 2; i <= m; ++i)
    {
        while (lal > b[i].l) add(a[--lal]);
        while (lar < b[i].r) add(a[++lar]);
        while (lal < b[i].l) del(a[lal++]);
        while (lar > b[i].r) del(a[lar--]);
        if (s != b[i].len)
        {
            ll x1 = s - b[i].len, x2 = b[i].len * (b[i].len - 1);
            ll g = __gcd(x1, x2);
            ans[b[i].i][0] = x1 / g;
            ans[b[i].i][1] = x2 / g;
        }
        else ans[b[i].i][1] = 1;
    }
    for (register int i = 1; i <= m; ++i)
        printf("%lld/%lld\n", ans[i][0], ans[i][1]);
}

洛谷 P1494 [国家集训队]小Z的袜子

原文：https://www.cnblogs.com/xuyixuan/p/9462162.html