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

    Type: Default 2000ms 512MiB

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

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

“今日扫描已完成。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 小队未知子网聊天日志,发言者和发言时间对应的唯一识别码已被恶意涂改,无法辨认

「退群杯」3rd

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
10
Start at
2022-2-12 13:30
End at
2022-2-12 18:30
Duration
5 hour(s)
Host
Partic.
205