题解：花神的嘲讽计划

核心思路

本题要判断在序列的某个区间 $[l, r]$ 中，是否存在长度为 $k$ 的连续子段与给定的嘲讽方案完全匹配。

主要方法

1. 滚动哈希（Rabin-Karp）
   将序列中每个长度为 $k$ 的子段通过哈希函数映射为一个无符号长整数（$\text{unsigned long long}$），便于快速比较。

2. 可持久化线段树
   建立可持久化权值线段树，每个版本 $rt[i]$ 存储前 $i$ 个长度为 $k$ 的子段的哈希值。
   查询时，只需检查版本 $rt[r-k+1]$ 与 $rt[l-1]$ 之间是否包含目标哈希值即可。

算法步骤

1. 读入序列，预处理哈希数组 $ha$ 和幂数组 $pw$。
2. 对每个长度为 $k$ 的子段计算哈希值，插入可持久化线段树。
3. 对于每个询问：
   • 计算嘲讽方案的哈希值 $hb$。
   • 若区间长度小于 $k$，直接输出 "No"（不会尴尬）。
   • 否则在线段树中查询区间 $[l, r-k+1]$ 是否包含 $hb$。
   • 若存在则输出 "No"，否则输出 "Yes"。

时间复杂度

• 预处理：$O(n \log U)$（$U$ 为哈希值域）
• 每次查询：$O(k + \log U)$
• 总体可行，满足数据范围 $n, m \leq 10^5$ 的要求。

关键点

• 利用哈希 $O(1)$ 比较任意长度为 $k$ 的子段。
• 通过可持久化线段树实现区间存在性查询，避免了暴力匹配的低效。## 题解：花神的嘲讽计划

核心思路

本题要判断在序列的某个区间 $[l, r]$ 中，是否存在长度为 $k$ 的连续子段与给定的嘲讽方案完全匹配。

主要方法

1. 滚动哈希（Rabin-Karp）
   将序列中每个长度为 $k$ 的子段通过哈希函数映射为一个无符号长整数（$\text{unsigned long long}$），便于快速比较。

2. 可持久化线段树
   建立可持久化权值线段树，每个版本 $rt[i]$ 存储前 $i$ 个长度为 $k$ 的子段的哈希值。
   查询时，只需检查版本 $rt[r-k+1]$ 与 $rt[l-1]$ 之间是否包含目标哈希值即可。

算法步骤

1. 读入序列，预处理哈希数组 $ha$ 和幂数组 $pw$。
2. 对每个长度为 $k$ 的子段计算哈希值，插入可持久化线段树。
3. 对于每个询问：
   • 计算嘲讽方案的哈希值 $hb$。
   • 若区间长度小于 $k$，直接输出 "No"（不会尴尬）。
   • 否则在线段树中查询区间 $[l, r-k+1]$ 是否包含 $hb$。
   • 若存在则输出 "No"，否则输出 "Yes"。

时间复杂度

• 预处理：$O(n \log U)$（$U$ 为哈希值域）
• 每次查询：$O(k + \log U)$
• 总体可行，满足数据范围 $n, m \leq 10^5$ 的要求。

关键点

• 利用哈希 $O(1)$ 比较任意长度为 $k$ 的子段。
• 通过可持久化线段树实现区间存在性查询，避免了暴力匹配的低效。