Summary

洛谷 P1494 [国家集训队]小 Z 的袜子 的题解,
算法为 莫队 .

Link

题目链接

Text

设区间 $[L,R]$ 内颜色为 $i$ 的袜子有 $s_i$ 只, 则抽到同一颜色的袜子的概率为

$$ \frac{\sum_{i=1}^n\frac{s_i*(s_i-1)}{2}}{\frac{(R-L+1)*(R-L)}{2}} $$

, 化简得到

$$ \frac{(\sum_{i=1}^ns_i^2)-(R-L+1)}{(R-L+1)*(R-L)} $$

.
设当前分子为 $ans$ 可以看出当 $s_i+1$ 时, 对 $ans$ 的影响为 $ans=ans-s_i^2+(s_i+1)^2$, 即 $ans+=s_i*2$,
当 $s_i+1$ 时, 对 $ans$ 的影响为 $ans=ans-s_i^2+(s_i-1)^2$, 即 $ans-=s_i*2-2$.

看出在两个相邻区间间跳转只需要 $O(1)$ 代价, 于是考虑使用 莫队 算法. 注意 在区间袜子数量增加时要先跳转再更新, 减少时要先更新后跳转.

Code

#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

long long n, m, c[50005], s[50005], q[50005], sqt, nlt, nrt, nas, ngd;
struct aqsk
{
    long long lft, rgt, num, asa, asb;
    bool operator<(const aqsk &cpr)
    {
        if (q[lft] == q[cpr.lft])
            return q[lft] & 1 ? rgt < cpr.rgt : rgt > cpr.rgt;
        return q[lft] < q[cpr.lft];
    }
} qes[50005];

bool cmp(aqsk cpa, aqsk cpb)
{
    return cpa.num < cpb.num;
}

int main()
{
    scanf("%lld%lld", &n, &m);
    sqt = sqrt(n);
    for (int i = 1; i <= n; i++)
        q[i] = i / sqt;
    for (int i = 0; i < n; i++)
        scanf("%lld", &c[i]);
    for (int i = 0; i < m; i++)
    {
        scanf("%lld%lld", &qes[i].lft, &qes[i].rgt);
        qes[i].lft--, qes[i].rgt--, qes[i].num = i;
        qes[i].lft == qes[i].rgt ? qes[i].asb = 1 : 0;
    }
    sort(qes, qes + m), s[c[0]] = 1;
    for (int i = 0; i < m; i++)
    {
        while (nlt < qes[i].lft)
            nas -= 2 * s[c[nlt]] - 2, s[c[nlt++]]--;
        while (nlt > qes[i].lft)
            nas += 2 * s[c[--nlt]], s[c[nlt]]++;
        while (nrt > qes[i].rgt)
            nas -= 2 * s[c[nrt]] - 2, s[c[nrt--]]--;
        while (nrt < qes[i].rgt)
            nas += 2 * s[c[++nrt]], s[c[nrt]]++;
        if (!nas)
        {
            qes[i].asb = 1;
            continue;
        }
        ngd = __gcd(qes[i].asa = nas, qes[i].asb = (nrt - nlt + 1) * (nrt - nlt));
        qes[i].asa /= ngd, qes[i].asb /= ngd;
    }
    sort(qes, qes + m, cmp);
    for (int i = 0; i < m; i++)
        printf("%lld/%lld\n", qes[i].asa, qes[i].asa ? qes[i].asb : 1);
    return 0;
}