不用主席树的做法，但思想和主席树差不多。 首先肯定是将所有 kkk 的区间转换成哈希值，不用多说。然后问题就是在 [l+k−1,r][l+k-1,r][l+k−1,r] 中有没有出现这个哈希值。 考虑转化。 我们可以先离散化以下，然后用桶储存 AAA 中每个哈希值出现的位置，查询时在对应的桶里二分，看看第一个大于等于 l+k−1l+k-1l+k−1 的值 xxx 和最后一个小于等于 rrr 的值 yyy，看看是否满足 x≤yx\le yx≤y。 时间复杂度：O((n+m)log⁡(n+m))O((n+m)\log (n+m))O((n+m)log(n+m))。