← 返回题目列表

Codeforces · 1302/H

H. 谁需要后缀结构?

中文机器翻译题面 查看原题

这是一次不寻常的比赛中的一个不寻常的问题,这里是公告:http://codeforces.com/blog/entry/73543

你经营一家琴弦店。在一天中,您的客户想要购买一定长度的字符串,有时还需要满足其他属性。

您有一个长度为 $$$n$$$ 的字符串,并且可以从其中的任意位置开始剪切任意长度的字符串。今天,您的第一位客户问您一些类型的问题“如果长度为 $$$k$$$ 的子字符串中的一个从位置 $$$i$$$ 开始,而另一个从第 $$$j$$$ 个位置开始,那么它们之间有什么区别吗?”你要回答所有这些问题。

请注意,在您的商店中,字符串超过了 $$$987\,898\,789$$$ 大小的字母表。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1\leq q, n\leq 200\,000$$$)。第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1$$$, ..., $$$a_n$$$ ($$$0\leq a_i < 987\,898\,789$$$) 表示字符串 $$$s$$$ 的字母,接下来的 $$$q$$$ 行包含三个整数 $$$len$$$, $$$pos_1$$$ 和 $$$pos_2$$$ ($$$1\leq len\leq n$$$, $$$1\leq pos_1, pos_2\leq n - len + 1$$$) 表示相应的查询。

输出

打印 $$$q$$$ 行,如果第 $$$i$$$ 查询中的两个子字符串(从 $$$pos_1$$$ 和 $$$pos_2$$$ 开始的长度 $$$len$$$ 相等,则打印第 $$$i$$$ 行,其中包含 Yes,否则包含 No。

示例

输入 #1

5 2
1 2 3 1 2
2 1 4
3 1 3

输出 #1

Yes
No

输入 #2

9 3
0 0 0 0 0 0 0 0 0
9 1 1
8 1 2
1 1 9

输出 #2

Yes
Yes
Yes