小红的双排列查询 — 从暴力到随机哈希

题目回顾

给定长为 $n$ 的数组 $a_1, a_2, \dots, a_n$ 和 $q$ 次询问，每次询问区间 $[l, r]$ 是否为双排列。

双排列：长度为 $2k$ 的数组，由两个 $1 \sim k$ 的排列打乱顺序组成。
等价于：包含且仅包含 $1 \sim k$ 每个数恰好 2 次。

排列：$1 \sim k$ 每个数恰好出现一次。

数据范围：$n, q \le 2.5 \times 10^5$，$a_i \le 2 \times 10^5$。

• 时间限制：1 秒
• 空间限制：1024 M

暴力做法（TLE）

while (q--) {
    int l, r; cin >> l >> r;
    vector<int> ct(maxx + 9);
    for (int i = l; i <= r; i++) ct[a[i]]++;   // 统计区间内每个数的出现次数

    // 条件1: 每个数的出现次数必须是偶数 (0 或 2)
    bool flag = true;
    for (int i = 0; i <= maxx; i++) {
        if (ct[i] % 2 == 1) { flag = false; break; }
    }
    if (!flag) { cout << "No\n"; continue; }

    // 条件2: 出现次数非零的数必须是从 1 开始的连续段
    int cnt = 0;
    for (int i = 0; i <= maxx; i++)
        if (ct[i] != 0) cnt++;
    for (int i = cnt + 1; i <= maxx; i++)
        if (ct[i] != 0) { flag = false; break; }

    cout << (flag ? "Yes" : "No") << '\n';
}

复杂度分析

每次询问需要 $O(\text{区间长度} + \max a_i)$ 统计 + 检查，最坏情况 $O(n)$ 每次询问，总复杂度 $O(nq)$，在 $2.5 \times 10^5$ 的数据范围下直接超时。

正解：随机哈希 + 前缀和

核心思路

区间 $[l, r]$ 长度 $\text{len} = r-l+1$ 为偶数（否则直接 No），设 $k = \text{len}/2$。

区间是双排列 $\iff$ $1 \sim k$ 各出现恰好 2 次，且没有其他数出现。

如果给 $1 \sim n$ 每个值分配一个随机 64 位整数作为「身份标识」，那么：

• 区间内 $x$ 出现 2 次 → 贡献 $2 \times \text{hash}[x]$
• 区间内 $x$ 出现 0 次 → 贡献 $0$
• 区间应该是双排列 → 总贡献应为 $2 \times (\text{hash}[1] + \text{hash}[2] + \cdots + \text{hash}[k])$

利用前缀和可以 $O(1)$ 得到区间贡献，$O(1)$ 得到目标值，从而每次询问 $O(1)$！

逐步推导

Step 1：生成随机哈希值

mt19937_64 myRand64(chrono::steady_clock::now().time_since_epoch().count());
for (int i = 1; i <= n; i++)
    has[i] = myRand64();   // has[i] = 随机 64 位无符号整数

Step 2：构建前缀和

只累加值 $\le n/2$ 的元素（原因见 Step 4）：

for (int i = 1; i <= n; i++) {
    int x; cin >> x;
    if (x > n / 2)
        pre[i] = pre[i - 1];          // 跳过，不贡献
    else
        pre[i] = pre[i - 1] + has[x]; // 累加 hash
}

这样 $\text{pre}[i]$ 表示前缀 $[1, i]$ 中所有 $\le n/2$ 的值 的哈希之和。

Step 3：构建目标哈希数组

for (int i = 1; i <= n; i++)
    has[i] = has[i] * 2 + has[i - 1];

展开看看：

$$ \begin{aligned} \text{has}[1] &= 2 \cdot r_1 + 0 = 2r_1 \\ \text{has}[2] &= 2 \cdot r_2 + \text{has}[1] = 2r_1 + 2r_2 \\ \text{has}[3] &= 2 \cdot r_3 + \text{has}[2] = 2r_1 + 2r_2 + 2r_3 \\ &\vdots \\ \text{has}[k] &= 2 \times (r_1 + r_2 + \cdots + r_k) \end{aligned} $$

其中 $r_i$ 是原始随机值。所以 $\text{has}[k]$ 就是「1~k 各出现 2 次」的目标哈希值。

Step 4：$O(1)$ 回答询问

while (q--) {
    int l, r; cin >> l >> r;
    int len = r - l + 1;
    bool ok = !(len & 1)                    // 长度必须是偶数
           && pre[r] - pre[l-1] == has[len / 2];  // 哈希值必须匹配
    cout << (ok ? "Yes\n" : "No\n");
}

为什么值 > n/2 要跳过？

区间长度 $\text{len} \le n$，所以 $k = \text{len}/2 \le n/2$。

在双排列中，只允许出现 $1 \sim k \le n/2$ 的数。任何 $> n/2$ 的数：

• 不应该出现在区间中
• 如果出现了，它不贡献到哈希和 → 总和会「缺少」这部分 → 与 $\text{has}[k]$ 不匹配 → 正确判 No

这也是为什么 $\text{has}$ 数组只需开到 $n$，因为 $k \le n/2 < n$。

正确性保证：哈希冲突概率

使用 64 位随机数 + mt19937_64，两个不同集合哈希值碰撞的概率约为 $2^{-64}$。

$q \le 2.5 \times 10^5$ 次询问，任意一次误判概率 $\approx q \times 2^{-64} \approx 1.35 \times 10^{-14}$，完全可以忽略。

复杂度

关键技巧总结

1. 随机哈希：用随机数给每个值打「指纹」，把「多重集相等」的判断转化为「整数相等」
2. 前缀和：区间哈希值 = 前缀差值，$O(1)$ 查询
3. 目标值预处理：$\text{has}[k] = 2\sum_{i=1}^k r_i$，用递推 $O(n)$ 算出所有目标值
4. 跳过不可能值：利用 $k \le n/2$ 的性质，直接忽略 $> n/2$ 的元素，简化逻辑