小Z的袜子

形式化题目

给定长度为 $N$ 的颜色序列 $C_1, C_2, \ldots, C_N$ ，以及 $M$ 个询问 $(L, R)$ 。对每个询问：从下标区间 $[L, R]$ 中等概率地选出两个不同位置的袜子，求两只袜子颜色相同的概率，并以最简分数 $A/B$ 输出；概率为 $0$ 时输出 0/1。

数据范围： $N, M \leqslant 50000$ ， $1 \leqslant L < R \leqslant N$ ， $C_i \leqslant N$ 。

以样例 C = [1, 2, 3, 3, 3, 2] 的询问 2 6 为例：区间内颜色为 $\{2, 3, 3, 3, 2\}$ ，同色的取法有 $\binom{3}{2} + \binom{2}{2} = 3 + 1 = 4$ 种，总取法 $\binom{5}{2} = 10$ 种，概率 $\frac{4}{10} = \frac{2}{5}$ 。

暴力解法

思路

对每个询问 $(L, R)$ 直接扫描区间一遍，用计数数组统计每种颜色的出现次数 $cnt_c$ ，则

P = \frac{\sum_c \binom{cnt_c}{2}}{\binom{R-L+1}{2}}

最后用 $\gcd$ 约分输出。单次询问 $O(N)$ ，总复杂度 $O(NM) = 2.5 \times 10^9$ ，在 $N, M \leqslant 50000$ 下完全不可接受。

代码

暴力解不单独给出：它只是下面正解在「每个询问独立重扫区间」时的退化形态，正解代码删掉排序部分即是暴力，验证也直接用正解代码完成。

复杂度

时间： $O(NM)$ 。
空间： $O(N)$ 。

瓶颈

瓶颈在于相邻询问的高度重叠被完全浪费：处理完 $(2,6)$ 再处理 $(3,5)$ ，两个区间只差一两个元素，暴力却把整个区间从头数一遍。如果能让「当前统计好的区间」在询问之间只伸缩端点地滑动，每次伸缩的代价又足够小，重叠部分就不用重算了。

正解

关键观察

分子可以随端点增减 $O(1)$ 维护。 设当前窗口为 $[l, r]$ ， $cnt_c$ 是窗口内颜色 $c$ 的只数，维护

cur = \sum_c \binom{cnt_c}{2}

把颜色为 $c$ 的一只袜子加入窗口时，它与窗口内已有的每只同色袜子各配成一对，所以同色对数恰好增加「加入前窗口内 $c$ 的只数」：

加入：cur += cnt[c]，然后 cnt[c] += 1；
删除：cnt[c] -= 1，然后 cur -= cnt[c]。

这两步是互逆的，且顺序不能颠倒（必须用改变前的计数算增量）。

思路

有了 $O(1)$ 的增量维护，问题变成：按什么顺序处理 $M$ 个静态区间询问，能让端点移动总量最小？ 这正是莫队算法：

块长取 $size \approx \sqrt{N^2/M}$ （ $M$ 与 $N$ 同阶时即 $\sqrt{N}$ ），把位置 $1 \sim N$ 分成若干块。
所有询问按（ $L$ 所在块编号， $R$ ）排序：块间从左到右；块内按 $R$ 排序。再做奇偶优化——奇数块内 $R$ 降序、偶数块内 $R$ 升序，避免换块时右指针整段回扫。
维护窗口 $[cur_l, cur_r]$ ，按顺序对每个询问把四个端点逐格伸缩到目标位置，用上面的增量公式维护 $cnt$ 和 $cur$ 。

可以证明端点总移动量为 $O((N+M)\sqrt{N})$ ：左端点每块内最多移动 $O(size)$ ，共 $O(M \cdot size)$ ；右端点在块内单调、整块间最多扫 $O(N)$ ，共 $O(N^2/size + M)$ 。取 $size = N/\sqrt{M}$ 时两项平衡为 $O(N\sqrt{M})$ 级别。

下面用样例的 $4$ 个询问（ $N=6$ ，取 $size=2$ ）演示窗口的滑动路径：

flowchart LR
    subgraph sort["按 块号(L), R 排序并奇偶优化"]
        order["(1,3) → (1,6) → (3,5) → (2,6)"]
    end
    subgraph move["窗口 [cur_l, cur_r] 的伸缩轨迹"]
        w0["初始 [1,0] 空窗口"] --> w1["扩张到 [1,3]<br>cur=0 → 0/1"]
        w1 --> w2["右端点扩到 6<br>[1,6] cur=4 → 4/15"]
        w2 --> w3["左端点缩到 3<br>[3,5] cur=3 → 1/1"]
        w3 --> w4["左端点扩回 2<br>[2,6] cur=4 → 2/5"]
    end
    sort --> move

观察重点：排序后右端点 $3 \to 6 \to 5 \to 6$ 只在小范围内来回，左端点按块单调向右；窗口每移动一格只做一次 $O(1)$ 增量，总代价就是端点走过的格子数，而不是每个询问的区间长度之和。

最后对每个询问输出： $total = \binom{r-l+1}{2}$ ；若 $cur = 0$ 输出 0/1，否则设 $g = \gcd(cur, total)$ ，输出 $\frac{cur/g}{total/g}$ 。答案按原始下标存回，保证按输入顺序输出。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 小 Z 的袜子：莫队算法维护窗口内同色对数。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

typedef long long ll;

const ll MAXN = 100005;

ll N, M;
ll a[MAXN];
ll cnt[MAXN]; // cnt[c]：当前窗口里颜色 c 的只数
ll cur = 0;   // 当前窗口内同色袜子对数 C(c,2) 之和
ll mo_size;

struct Query {
    ll l, r, id;
};

Query qs[MAXN];
ll ans_num[MAXN], ans_den[MAXN];

// 右端点加入第 i 只袜子，登记它与窗口内同色袜子配成的新对
void expand(ll i) {
    ll c = a[i];
    cur += cnt[c];
    cnt[c]++;
}

// 左端点移出第 i 只袜子，撤销它贡献的同色对
void shrink(ll i) {
    ll c = a[i];
    cnt[c]--;
    cur -= cnt[c];
}

ll block_less(const Query& x, const Query& y) {
    ll bx = x.l / mo_size, by = y.l / mo_size;
    if (bx != by) return bx < by;
    return (bx % 2 == 0) ? (x.r < y.r) : (x.r > y.r);
}

ll gcd2(ll x, ll y) {
    while (y) {
        ll t = x % y;
        x = y;
        y = t;
    }
    return x;
}

ll isqrt_ll(ll v) {
    if (v <= 0) return 0;
    ll r = (ll)std::sqrt((double)v);
    while (r > 0 && r * r > v) r--;
    while ((r + 1) * (r + 1) <= v) r++;
    return r;
}

int main() {
    if (scanf("%lld %lld", &N, &M) != 2) return 0; // 空输入安全返回
    ll maxc = 0;
    for (ll i = 0; i < N; i++) {
        scanf("%lld", &a[i]);
        if (a[i] > maxc) maxc = a[i];
    }
    for (ll i = 0; i <= maxc && i < MAXN; i++) cnt[i] = 0;

    for (ll i = 0; i < M; i++) {
        scanf("%lld %lld", &qs[i].l, &qs[i].r);
        qs[i].l--;
        qs[i].r--;
        qs[i].id = i;
    }

    mo_size = N / (M > 0 ? (isqrt_ll(M) > 0 ? isqrt_ll(M) : 1) : 1);
    if (mo_size < 1) mo_size = 1;
    std::sort(qs, qs + M, block_less);

    ll cur_l = 0, cur_r = -1; // 空窗口用 cur_r < cur_l 表示
    for (ll t = 0; t < M; t++) {
        ll l = qs[t].l, r = qs[t].r, id = qs[t].id;
        while (cur_l > l) {
            cur_l--;
            expand(cur_l);
        }
        while (cur_r < r) {
            cur_r++;
            expand(cur_r);
        }
        while (cur_l < l) {
            shrink(cur_l);
            cur_l++;
        }
        while (cur_r > r) {
            shrink(cur_r);
            cur_r--;
        }
        ll total = (r - l + 1) * (r - l) / 2;
        ll same = cur;
        if (same == 0) {
            ans_num[id] = 0;
            ans_den[id] = 1;
        } else {
            ll g = gcd2(same, total);
            ans_num[id] = same / g;
            ans_den[id] = total / g;
        }
    }

    for (ll i = 0; i < M; i++) {
        printf("%lld/%lld\n", ans_num[i], ans_den[i]);
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 18:04
# update_at: 2026-10-01 18:04

import sys
from math import gcd

N, M = 0, 0
cnt: list[int] = []  # cnt[c]：当前窗口里颜色 c 的袜子只数
cur = 0              # 当前窗口内同色袜子对数 C(c,2) 之和


def expand(i: int) -> None:
    """右端点加入第 i 只袜子，登记它与窗口内同色袜子配成的新对。"""
    global cur
    c = a[i]
    cur += cnt[c]     # 新增同色对数 = 窗口内已有该颜色只数
    cnt[c] += 1


def shrink(i: int) -> None:
    """左端点移出第 i 只袜子，撤销它贡献的同色对。"""
    global cur
    c = a[i]
    cnt[c] -= 1
    cur -= cnt[c]     # 先减后撤：剩下的同色只数就是它原来配成的对数


def mo_order(q: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
    """把询问按（左端点所在块，右端点）排序：块间从左到右，块内右端点单调。"""
    size = max(1, N // max(1, int(M**0.5)))  # 块长 √(N²/M)，退化为 M=1 也能工作
    return sorted(q, key=lambda x: (x[0] // size, x[1] if x[0] // size % 2 == 0 else -x[1]))


def solve() -> None:
    global N, M, cnt
    data = iter(sys.stdin.buffer.read().split())
    N, M = int(next(data)), int(next(data))
    global a
    a = [int(next(data)) for _ in range(N)]
    cnt = [0] * (max(a) + 1)  # 颜色值域内开计数数组

    # 询问带上原始下标，排完序算完后还能按输入顺序输出
    queries = [(int(next(data)) - 1, int(next(data)) - 1, i) for i in range(M)]

    order = mo_order(queries)
    ans: list[str] = [""] * M

    cur_l, cur_r = 0, -1  # 当前窗口 [cur_l, cur_r]，空窗口用 cur_r < cur_l 表示
    for l, r, i in order:
        while cur_l > l:  # 左端点左移：扩张
            cur_l -= 1
            expand(cur_l)
        while cur_r < r:  # 右端点右移：扩张
            cur_r += 1
            expand(cur_r)
        while cur_l < l:  # 左端点右移：收缩
            shrink(cur_l)
            cur_l += 1
        while cur_r > r:  # 右端点右移：收缩
            shrink(cur_r)
            cur_r -= 1

        total = (r - l + 1) * (r - l) // 2  # 从区间里任取两只袜子的方案数
        same = cur
        if same == 0:
            ans[i] = "0/1"
        else:
            g = gcd(same, total)
            ans[i] = f"{same // g}/{total // g}"

    print("\n".join(ans))


if __name__ == "__main__":
    solve()

复杂度

时间：排序 $O(M \log M)$ + 端点移动 $O((N+M)\sqrt{N})$ 次 $O(1)$ 增量。 $N = M = 50000$ 时约 $10^7$ 量级基本操作。
空间： $O(N + M)$ （颜色计数数组与询问列表）。

总结

概率公式的核心是把「随机选两只」看成无序二元组：分子 $\sum_c \binom{cnt_c}{2}$ ，分母 $\binom{len}{2}$ 。
把分子改写成「加入一只袜子时增量可算」的形式，静态区间统计就从"每次重扫"变成"端点增量维护"。
莫队 = 离线排序（分块 + 奇偶优化）+ $O(1)$ 增量伸缩，适用于无修改的区间询问；本题是莫队的经典入门模型。

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

关键观察

思路

代码

复杂度

总结