P1494 小 Z 的袜子

小 Z 的袜子：用莫队维护同色配对数

问题

P1494 [国家集训队] 小 Z 的袜子
多次询问区间 $[l,r]$ 中随机抽取两只袜子时，两只袜子颜色相同的概率，并输出最简分数。

数据规模：$N,M\le 5\times 10^4$，颜色 $C_i\le N$。

这是一道离线区间查询。若已经知道当前区间的答案，移动一个端点时可以在常数时间内更新；但原询问顺序中的端点可能大幅跳跃，也没有容易直接合并的简单节点信息。

于是我们可以考虑莫队，原理详见 P2709 小 B 的询问。

一次询问中，设颜色 $x$ 出现了 $cnt_x$ 次，那么从中选出两只同色袜子的方案数为 $\displaystyle \binom{cnt_x}{2}$。所有同色方案数是 $\displaystyle \sum_x\binom{cnt_x}{2}$，而从长度为 $len$ 的区间中任选两只袜子的方案数是 $\displaystyle \binom{len}{2}$。

所以问题变成：多次区间询问中维护每种颜色的出现次数，以及所有颜色配对数之和。由于区间没有修改，可以使用莫队调整询问顺序，使相邻询问之间只移动少量端点。

记当前分子为 $\displaystyle S=\sum_x\binom{cnt_x}{2}$，加入或删除颜色 $x$ 时，先减去它修改前的贡献，再改变 cnt[x]，最后加回修改后的贡献。

处理完询问后，将 $\displaystyle S / \binom{len}{2}$ 约分即可；当 $len=1$ 时没有合法的二元选择，按题意输出 0/1。

时间复杂度约为 $O((N+M)\sqrt N)$，空间复杂度为 $O(N+M)$。

▶

P1494

struct Frac {
/* ============================== */
ll p, q;
Frac( ll p = 0, ll q = 1 ) : p( p ), q( q ) {}
void reduce( ) {
    if( p == 0 ) {
        q = 1;
        return;
    }
    ll g = gcd( p, q );
    p /= g, q /= g;
}
/* ============================== */
};

int a[maxn];
Frac ans[maxn];
ll cnt[maxn];

struct Query {
    int l, r, idx;
} qs[maxn];

int block;
ll nowans;
int get_block( int pos ) {
    return ( pos - 1 ) / block;
}

bool cmp( Query x, Query y ) {
    int bx = get_block( x.l ), by = get_block( y.l );
    if( bx != by ) return bx < by;
    if( bx & 1 ) return x.r < y.r;
    return x.r > y.r;
}

ll nC2( ll n ) {
    return n * ( n - 1 ) / 2;
}

void add( int pos ) {
    int x = a[pos];
    nowans -= nC2( cnt[x] );
    cnt[x] ++;
    nowans += nC2( cnt[x] );
}

void del( int pos ) {
    int x = a[pos];
    nowans -= nC2( cnt[x] );
    cnt[x] --;
    nowans += nC2( cnt[x] );
}

void solve( ) {
    int n = read( ), m = read( );
    block = sqrt( n );
    nowans = 0;

    for( int i = 1; i <= n; ++ i ) a[i] = read( );
    for( int i = 1; i <= m; ++ i ) {
        qs[i].l = read( ), qs[i].r = read( );
        qs[i].idx = i;
    }

    sort( qs + 1, qs + m + 1, cmp );
    int L = 1, R = 0;

    for( int i = 1; i <= m; ++ i ) {
        auto [l, r, idx] = qs[i];
        while( L > l ) add( -- L );
        while( R < r ) add( ++ R );
        while( L < l ) del( L ++ );
        while( R > r ) del( R -- );

        int len = r - l + 1;
        if( len == 1 ) {
            ans[idx] = { 0, 1 };
        }
        else {
            ans[idx] = { nowans, nC2( len ) };
            ans[idx].reduce( );
        }
    }

    for( int i = 1; i <= m; ++ i ) {
        cout << ans[i].p << '/' << ans[i].q << '\n';
    }
}

记录

• 归属：[[区间频次统计模型]]、[[莫队]]

• 新增：把同色概率的分子写成各颜色配对数之和后，每次端点移动只会改变一种颜色的组合数贡献。

• 分类：待定