#H1079. E. ‘Minami Kotori’ Pantw 和他的召唤物二元葡萄

    ID: 239 Type: Default 2000ms 512MiB Tried: 121 Accepted: 17 Difficulty: 8 Uploaded By: Tags>字符串后缀数组后缀自动机退群杯

E. ‘Minami Kotori’ Pantw 和他的召唤物二元葡萄

题目背景

“今日扫描已完成。Pantw,男,21岁,当前综合评价:AA-。”

“快到 4.0 了吗……能得到你的认可真不容易啊。”

“这得益于宿主与 MSF_Akatsuki 先生的通力合作,走出了一条令人……呃,令评价算法意外的偶像道路。”

“嗯……但是说实话,系统,你真的愿意看到我走到那个无法估量的境界吗?”

“当然,宿主。4.0 是每个人都想追求的。”

“好吧,你说是那就是。但这一票,对我们很重要。你别给我出什么幺蛾子。”

“系统会尽力的。”

题目描述

葡萄味花了老半天才给他身上的系统解释清楚,自己现在叫“南小鸟”而不是“南琴梨”(尽管系统觉得平假名写法都一样实在搞不懂宿主为什么要区分开)。这个伴随他降临而诞生的系统似乎并不是真心想让它的宿主变强,尽管它和其他系统一样呆萌、腹黑和关键时刻似乎并不脱线,但作为一名现充,穿越前的三次元生活经验还是让他持续着若即若离的姿态。不过系统似乎也没有给他带来很多好处,现在唯一的召唤物就是这个和他名字很配的二元葡萄。

这个二元葡萄 SS 是一个链状的葡萄串,葡萄串上的每个葡萄都是 26 个品种中的其中一种(为了方便,用小写字母表示当前每个字母的品种)。它的“二元”性体现在使用方法上:选取它的两个子串 A,BA,B,二元葡萄就会告诉你 BB 有多少个包含 AA 的子串。这个能力看起来毫不起眼,但在潘达和 knb 的帮助下,他们已经破解了无数个城市数据库里的机密情报。当然,它的能力使用也有限制,使用 qq 次后就会过热一段时间。如今他们又有了新的任务,作为二元葡萄,你不需要关心其他的事情,做好你的本职工作就可以了。

数据格式与约定

输入

输入第一行为一个字符串 S(S2×105)S(|S| \le 2\times10^5),表示二元葡萄,下标从 11 开始。

接下来一行包含一个整数 q(q2×105)q(q \le 2\times10^5),表示使用二元葡萄的次数。

接下来 qq 行,每行包含四个正整数 $a, b, c, d (1 \le a \le b \le |S|, 1 \le c \le d \le |S|)$,SabS_{a \to b} 对应第一个子串 AAScdS_{c \to d} 对应第二个子串 BB

输出

输出包含 qq 行,每行一个整数 ansans,表示对应的答案。

样例

wwqwq
3
1 2 3 5
2 3 1 5
4 4 1 5
0
8
13

后记

“如果我们不是第一个尝试解开这一切的队伍,如果有人告诉我,曾经的那些人都已经不见了,如果有人觉得这个世界变成这样也没什么大不了……你该怎么办?我们要怎么办?”

“通常情况下这么多如果只会出现在轻小说剧情里。至于我们,寄就寄呗,反正都不知道咋回去,推动剧情进度就算成功。”

——OIER 小队未知子网聊天日志,发言者和发言时间对应的唯一识别码已被恶意涂改,无法辨认