#P14864. [OOI2025 资格赛]Alien Homophones外星同音词

    ID: 14080 传统题 2000ms 1024MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-普通并查集AC 自动机DAG 动态规划倍增跳转双哈希模逆元

[OOI2025 资格赛]Alien Homophones外星同音词

题目描述

Okarun 一直痴迷于外星人存在的想法。他小时候尝试过各种联系外星人的方式,但都没有成功。这并不奇怪,因为外星人说的是一种完全不同的语言!

有一天,他读到一篇文章,说外星人实际上也使用小写拉丁字母书写,但读词的方式完全不同。

在外星语言中,有 n+26n+26 种不同的声音,每种声音由一个拉丁字母串 sis_i 表示。已知对于 1≤i≤261\le i\le 26,第 ii 种声音由长度为 11 的字符串表示,即第 ii 个小写拉丁字母。对于 i>26i>26,第 ii 种声音由长度至少为 22 的小写拉丁字母串表示。

当外星人读一个单词 xx 时,他从第一个位置开始。若当前位于位置 ii,他会寻找一个声音 sjs_j,使得 sjs_j 从位置 ii 开始作为 xx 的子串出现。如果有多个这样的声音,他选择长度最大的那个声音 sjs_j。然后他读出该声音,并移动到位置 i+∣sj∣i+|s_j|,继续读,直到整个单词读完。注意,由于每个小写拉丁字母本身都是一种声音,因此任何单词都总能被读出。

后来还发现,有些外星声音虽然写法不同,但实际发音相同。也就是说,存在一些声音字符串 sis_i 和 sjs_j(i≠ji\ne j,si≠sjs_i\ne s_j),它们表示相同的声音。并且这种相同关系具有传递性:如果 sis_i 与 sjs_j 被认为相同,sjs_j 与 sls_l 被认为相同,那么 sis_i 与 sls_l 也被认为相同。

外星人称某些单词为同音词:它们听起来相同,拼写可以相同也可以不同。换句话说,若两个单词 v,wv,w 按外星语言读出后得到的声音序列完全相同,则它们是同音词。

Okarun 写了一段由小写拉丁字母组成的文本 tt。他想研究 qq 对文本子串。每对中,第一个子串是文本中从第 aia_i 个字符到第 bib_i 个字符(含两端),第二个子串是从第 cic_i 个字符到第 did_i 个字符(含两端)。对于每一对子串,Okarun 想知道它们在外星语言中是否是同音词。

子串的定义:一个字符串的子串可以通过从原字符串开头删除若干字符,并从结尾删除若干字符得到,删除数量可以为零。

输入格式

第一行包含一个非空字符串 tt(1≤∣t∣≤5000001\le |t|\le 500000),由小写拉丁字母组成。

第二行包含两个整数 n,kn,k(0≤n≤5000000\le n\le 500000,0≤k<n+260\le k<n+26),分别表示长度至少为 22 的声音数量,以及 Okarun 记录的相同声音对数量。

接下来 nn 行描述从第 2727 种声音开始的声音。第 ii 行包含一个非空字符串 si+26s_{i+26}(2≤∣si+26∣≤1062\le |s_{i+26}|\le 10^6),由小写拉丁字母组成,表示第 i+26i+26 种声音。保证所有声音字符串两两不同。注意,输入中不会出现 a 到 z 这些单字母声音,但每个测试中它们都默认作为编号 11 到 2626 的声音存在。

接下来 kk 行描述 Okarun 最初记录的相同声音对。每行包含两个整数 xi,yix_i,y_i(1≤xi,yi≤n+261\le x_i,y_i\le n+26,xi≠yix_i\ne y_i),表示 Okarun 认为编号为 xix_i 与 yiy_i 的两个声音发音相同。保证每对编号最多出现一次。注意,其他声音对的相同关系可能由传递性推出。

下一行包含一个整数 qq(1≤q≤3000001\le q\le 300000),表示需要判断的子串对数量。

接下来 qq 行,每行包含四个整数 ai,bi,ci,dia_i,b_i,c_i,d_i(1≤ai≤bi≤∣t∣1\le a_i\le b_i\le |t|,1≤ci≤di≤∣t∣1\le c_i\le d_i\le |t|),表示两个子串:第一个为文本 tt 中位置 aia_i 到 bib_i,第二个为位置 cic_i 到 did_i。

设 SS 为所有额外声音字符串长度之和,即不包含 a 到 z 的声音时,

S=∑∣si∣.S=\sum |s_i|.

保证 S≤106S\le 10^6。

输出格式

输出 qq 行。对于第 ii 个询问,如果两个子串在外星语言中同音,输出 Yes;否则输出 No。

样例

abracadabra
2 3
cada
ca
1 27
1 28
1 4
4
5 11 1 4
4 6 5 7
5 7 5 8
2 5 2 5
Yes
Yes
No
Yes

样例解释

第一个询问中:

  • 第一个子串 cadabra 会被读作声音:cada, b, r, a;
  • 第二个子串 abra 会被读作声音:a, b, r, a。

声音 cada 与 a 被记录为相同(编号对 (1,27)(1,27)),因此这两个子串是外星同音词。

第二个询问中:

  • 第一个子串 aca 会被读作声音:a, ca;
  • 第二个子串 cad 会被读作声音:ca, d。

声音 a 与 ca 被记录为相同(编号对 (1,28)(1,28)),声音 ca 与 d 也相同(因为编号 (1,4)(1,4) 与 (1,28)(1,28) 的声音相同,所以编号 44 与 2828 也相同)。因此这两个子串也是外星同音词。

第三个询问中:

  • 第一个子串 cad 会被读作声音:ca, d;
  • 第二个子串 cada 会被读作声音:cada。

声音数量不同,因此它们一定不是外星同音词。

第四个询问给出了两个相同子串,因此读法相同,是外星同音词。

评分方式

本题测试点由 10 个分组组成。只有通过某一组及其要求的部分前置分组时,才能获得该组分数。注意,部分分组不要求通过样例。Offline-testing 表示该组测试结果只会在比赛结束后给出。

| 组别 | 分数 | 附加限制:∣t∣|t| | 附加限制:SS | 附加限制:qq | 依赖分组 | 说明 | | ---- | ---: | --------------: | ------------: | ------------: | -------- | --------------- | | 0 | 0 | - | - | - | - | 样例 | | 1 | 8 | ∣t∣≤500|t|\le 500 | S≤500S\le 500 | q≤500q\le 500 | 0 | - | | 2 | 7 | ∣t∣≤6000|t|\le 6000 | S≤6000S\le 6000 | q≤6000q\le 6000 | - | bi=di=∣t∣b_i=d_i=|t| | | 3 | 9 | ∣t∣≤6000|t|\le 6000 | S≤6000S\le 6000 | q≤200000q\le 200000 | 2 | bi=di=∣t∣b_i=d_i=|t| | | 4 | 15 | ∣t∣≤200000|t|\le 200000 | S≤200000S\le 200000 | q≤200000q\le 200000 | 2,3 | bi=di=∣t∣b_i=d_i=|t| | | 5 | 8 | ∣t∣≤6000|t|\le 6000 | S≤6000S\le 6000 | q≤200000q\le 200000 | - | ai=ci=1a_i=c_i=1 | | 6 | 6 | ∣t∣≤500|t|\le 500 | S≤500S\le 500 | q≤200000q\le 200000 | 0,1 | - | | 7 | 7 | ∣t∣≤6000|t|\le 6000 | S≤6000S\le 6000 | q≤6000q\le 6000 | 0–2 | - | | 8 | 10 | ∣t∣≤6000|t|\le 6000 | S≤200000S\le 200000 | q≤6000q\le 6000 | 0–2,7 | - | | 9 | 19 | ∣t∣≤200000|t|\le 200000 | S≤400000S\le 400000 | q≤200000q\le 200000 | 0–8 | - | | 10 | 11 | - | - | - | 0–9 | Offline-testing |