#YDRG006F. 字符串匹配问题

字符串匹配问题

题目背景

首先给出如下定义:

  • 子串 [l,r][l,r] :依次取出字符串中 ll 个字符到第 rr 个字符后,顺序拼接得到的新字符串。
  • 子串内的单个字符 [l,r]x[l,r]_x :表示子串 [l,r][l,r] 从左向右的第 xx 个字符。
  • 子串的匹配:两个子串长度相等,且对应位置上的字符相同。

题目描述

给定一个长度为 nn 的字符串和 qq 次询问。每次询问会取出这个字符串的两个子串 [l1,r1][l_1,r_1][l2,r2][l_2,r_2] ,并询问这两个子串是否匹配。

但出题人很粗心。在取出字符串时,他不小心把子串 [l1,r1][l_1,r_1] 的每个字符都用另一个字符替换掉了(可能替换后和原来一样)。同时,替换过程存在如下性质:若原来子串 [l1,r1][l_1,r_1] 的某个位置上的字符 pp 的字典序大于或小于该子串内另一个位置上的字符 qq 的字典序,那么在替换后,这种偏序关系仍然成立。设 [l1,r1][l_1,r_1]' 为替换后的字符串,则以上性质可以被如此表述:

$$\forall l_1\leq p,q\leq r_1,\\ [l_1,r_1]_p < [l_1,r_1]_q \Longleftrightarrow [l_1,r_1]'_p < [l_1,r_1]'_q $$

但问题在于:我们只知道子串 [l1,r1][l_1,r_1] 根据上述规则被替换了,但并不知道该子串中的每个字符具体被替换成了什么。现在好奇的出题人想知道,被替换后的子串 [l1,r1][l_1, r_1] 和未做改动的子串 [l2,r2][l_2, r_2] 是否有可能 匹配呢?

注意,询问与询问之间彼此独立。

输入格式

11 行共两个整数 n,qn,q 表示串长和询问数。

22 行共 nn 个整数表示这个字符串每个位置上的字符的字典序

3q+23\sim q+2 行,每行 44 个正整数分别表示 l1,r1,l2,r2l_1,r_1,l_2,r_2

输出格式

对于每个询问,输出 YesNo 表示是否 可能 匹配。

样例 #1

样例输入 #1

6 3
1 1 4 5 5 9
1 3 4 6
1 2 2 3
1 2 4 5

样例输出 #1

Yes
No
Yes

提示

我们令 aia_i 表示第 ii 个字符的字典序。

对于 100%100\% 的数据,保证 1n,q,ai1051 \leq n,q,a_i \leq 10^5r1l1=r2l2r_1 - l_1 = r_2 - l_2

开启子任务捆绑。

测试点编号 nn \leq qq \leq 特殊性质
131 \sim 3 10310^3
474 \sim 7 10510^5 保证 ai2a_i \leq 2
898 \sim 9 保证 ai>ai1a_i > a_{i-1}
102010 \sim 20

每个子任务分值为子任务中测试点数量乘 55