BZOJ 2038 小 Z 的襪子 —— 莫隊算法離線區間查詢同色概率

BZOJ 2038：N, M ≤ 5×10⁴，N 隻襪子，M 次查詢 [L, R]，求隨機抽取兩隻顏色相同的概率（最簡分數）。經典莫隊算法離線模板題。

一、數學轉化

區間長度 len = R-L+1，總方案數 C(len, 2) = len*(len-1)/2。
設顏色 c 出現 cnt[c] 次，同色方案數 Σ C(cnt[c], 2) = Σ cnt[c]*(cnt[c]-1)/2。
概率 = (Σ cnt[c]² - len) / (len² - len)。
只需維護 Σ cnt[c]² 與 len，單次增減元素 O(1) 更新。

二、莫隊算法核心

• 分塊大小 B = √N。
• 查詢按 (L/B, R) 排序：左端點塊為主鍵，右端點為次鍵。
• 維護當前區間 [curL, curR]，逐個移動端點調整 cnt[] 與 sumSq。

三、增減元素邏輯

void add(int pos, int delta) { // delta = +1 加入, -1 移除
    int c = color[pos];
    sumSq -= 1LL * cnt[c] * cnt[c];
    cnt[c] += delta;
    sumSq += 1LL * cnt[c] * cnt[c];
}

四、完整 AC 代碼（關鍵片段）

struct Query { int l, r, id; ll x, y; } q[maxn];
int block = sqrt(n);
bool cmp(Query a, Query b) {
    int blka = a.l / block, blkb = b.l / block;
    return blka == blkb ? a.r < b.r : blka < blkb;
}

sort(q+1, q+m+1, cmp);
int curL = 1, curR = 0;
for (int i = 1; i <= m; ++i) {
    while (curL > q[i].l) add(--curL, +1);
    while (curR < q[i].r) add(++curR, +1);
    while (curL < q[i].l) add(curL++, -1);
    while (curR > q[i].r) add(curR--, -1);

    int len = q[i].r - q[i].l + 1;
    if (len <= 1) { q[i].x = 0; q[i].y = 1; continue; }
    q[i].x = sumSq - len;
    q[i].y = 1LL * len * (len - 1);
    ll g = gcd(q[i].x, q[i].y);
    q[i].x /= g; q[i].y /= g;
}
sort(q+1, q+m+1, [](Query a, Query b){ return a.id < b.id; });
for (int i = 1; i <= m; ++i) printf("%lld/%lld\n", q[i].x, q[i].y);

五、複雜度與優化

• 時間：O((N+M)√N) ≈ 1.5×10⁷ 操作，極快。
• 空間：O(N + maxColor)。
• 優化：block = N / sqrt(M) 更優；用 inline、快速 IO、避免除法（用乘法逆元或延後約分）。

六、樣例驗證

Input:
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

Output:
2/5
0/1
1/1
4/15