题目理解回顾

我们有一个颜色序列，可以删除一些颜色（删除某个颜色会删掉序列中所有该颜色的位置）。
要求：删除后剩下的序列是 非空且连续 的。
换句话说，不能出现“中间挖空”导致序列断裂的情况。

---

核心思路

1. 问题转化

删除颜色后序列连续 ⇔ 被保留的颜色在序列中的出现位置构成一个连续区间。

更形式化地说：
设我们保留的颜色集合为 $S$，那么对于任意在 $S$ 中的颜色，它的所有出现位置必须完整落在某个连续区间内，且这个区间内不能包含任何被删除的颜色的位置。

---

算法核心：哈希与前缀和

2. 关键观察

如果我们将每种颜色映射为一个 随机权值，并且保证该颜色所有出现位置的权值和为 $0$（在模意义下），那么：

• 当我们考虑一个区间 $[l, r]$ 时，如果这个区间内 每种颜色要么完整出现，要么完全不出现，那么该区间权值前缀和 $\text{sum}[r] - \text{sum}[l-1] = 0$。
• 反之，如果区间内某种颜色只出现一部分，那么权值前缀和不为 $0$。

3. 哈希设计

代码使用了 双哈希 来减少碰撞：

• $\text{mod1} = 10^9+7$, $\text{mod2} = 10^9+9$
• 对每种颜色，除了最后一次出现外，每次出现赋予一个随机值
• 最后一次出现的权值设为 负的前面所有权值和，这样该颜色总权值和为 $0$

具体实现：

for (int i = 1; i <= n; i++) {
    if (i == last[a[i]])
        val1[i] = (mod1 - s1[a[i]]) % mod1;
    else {
        s1[a[i]] += (val1[i] = rd1());
        if (s1[a[i]] >= mod1) s1[a[i]] -= mod1;
    }
}

4. 前缀和与计数

计算前缀和：

$\text{sum1}[i] = \sum_{j=1}^i \text{val1}[j] \pmod{\text{mod1}}$ $\text{sum2}[i] = \sum_{j=1}^i \text{val2}[j] \pmod{\text{mod2}}$

重要性质：
如果区间 $[l, r]$ 满足"每种颜色要么完整出现，要么完全不出现"，那么：

$\text{sum1}[r] - \text{sum1}[l-1] \equiv 0 \pmod{\text{mod1}}$ $\text{sum2}[r] - \text{sum2}[l-1] \equiv 0 \pmod{\text{mod2}}$

即： $\text{sum1}[r] = \text{sum1}[l-1], \quad \text{sum2}[r] = \text{sum2}[l-1]$

---

5. 统计有效区间

我们遍历所有右端点 $r$，统计有多少 $l-1$ 满足：

$(\text{sum1}[l-1], \text{sum2}[l-1]) = (\text{sum1}[r], \text{sum2}[r])$

这样区间 $[l, r]$ 就是合法的保留区间。

使用 std::map<std::pair<int, int>, int> 来计数之前出现过的哈希对数量。

6. 算法流程

1. 预处理：

   • 找到每种颜色最后出现的位置
   • 为每种颜色的非最后一次出现生成随机权值
   • 最后一次出现权值 = 负的前面权值和（保证总权值和为 0）

2. 计算前缀和：

   • 计算双哈希前缀和数组

3. 统计答案：

   • 用哈希表记录每个前缀和二元组出现次数
   • 遍历右端点，累加相同前缀和的出现次数

---

7. 复杂度分析

• 时间复杂度：$O(n \log n)$（主要来自 map 操作）
• 空间复杂度：$O(n)$

---

8. 正确性说明

为什么这样哈希能工作？

• 如果区间 $[l, r]$ 包含某种颜色的部分出现，那么该颜色的权值和不等于 0，导致前缀和差不为 0
• 如果区间 $[l, r]$ 完整包含某些颜色或不包含，那么这些颜色的权值和为 0，不影响前缀和差
• 双哈希极大降低了哈希碰撞概率

为什么统计 sum[r] == sum[l-1]？

因为 $\text{sum}[r] - \text{sum}[l-1] = 0$ 表示区间 $[l, r]$ 内所有颜色的权值和为 0，即每种颜色要么完整出现，要么完全不出现。

---

9. 样例验证

对于样例：1 3 2 4 3

颜色出现情况：

• 颜色1：位置1
• 颜色2：位置3
• 颜色3：位置2,5
• 颜色4：位置4

哈希后，满足条件的区间对应的 $(l-1, r)$ 前缀和相同，共6个：

• 空删除（保留全部）
• 只删除颜色1
• 只删除颜色1,3
• 只删除颜色1,2,3
• 只删除颜色1,3,4
• 只删除颜色2,3,4

---

总结

这道题的精妙之处在于：

1. 将“序列连续”条件转化为“颜色完整出现”条件
2. 使用随机哈希+模运算构造权值，保证颜色完整出现时权值和为0
3. 利用前缀和相同来快速统计合法区间
4. 双哈希确保正确性

这是一种典型的 哈希+前缀和 解决子区间统计问题的方法，在竞赛中非常实用。