#PQJ871x3277. QOJ 871_3277

    ID: 3049 传统题 8000ms 2048MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2021字符串区间DP

QOJ 871_3277

标题: 扑克比大小 - Problem - QOJ.ac

#3277. 扑克比大小

Statistics

The problem was used in the following contests:

小 Z 和小 A 在玩扑克比大小。

他们玩的扑克比大小规则如下:

  • 在游戏开始前,系统会给小 Z 和小 A 各发一堆手牌(两堆牌数量可能不相同),其中每张牌上写有一个小写字母。
  • 在游戏的每一轮,小 Z 和小 A 同时翻开牌堆顶的第一张牌,若两人翻开的牌不同,则牌上对应小写字母更小的那一方获胜;若两人翻开的牌相同,则他们会将翻开的牌塞入牌堆底,继续游戏,直到某方获胜为止。

而系统实际上是从一个巨大的牌库里面发牌的,具体来说,假设牌库共有 n 张牌,分别是 a1,a2,⋯,an,则系统会随机选择第 l 张到第 r 张牌发给玩家,换言之,玩家从牌堆顶到牌堆底的牌分别是 al,al+1,⋯,ar。

现在小 Z 和小 A 一共要进行 q 轮游戏,并且小 Z 通过某种方式得知了系统在第 i 轮发给小 A 的牌为 ali,ali+1,⋯,ari,小 Z 想知道他一共有多少种可能的手牌能赢小 A。两堆手牌视为不同当且仅当两堆手牌数量不同,或存在一个位置 d 使得两堆手牌中距离堆顶为 d 的牌不同。

输入格式

从标准输入读入数据。

输入的第一行包含一个只包含小写字母的字符串 a 。

输入的第二行包含一个正整数 q 和一个整数 type,其中 type 表示数据类型。

接下来 q 行,第 i 行包含两个整数 li 和 ri。

输出格式

输出到标准输出。

输出 q 行,每行一个整数表示小 Z 有多少种可能的手牌能赢小 A。

样例数据

样例 1 输入

abbab
5 0
1 3
2 4
3 5
1 4
2 5

样例 1 输出

4
7
6
2
8

样例 2

见下发文件。

样例 3

见下发文件。

数据范围与提示

对于所有数据,满足 1≤li≤ri≤|a|≤5×105,1≤q≤5×105。

子任务 得分 n≤ q≤ type 1 3 102 102 0 2 3 500 2000 3 4 2000 4 5 2×104 5 13 105 105 3 6 17 0 7 15 5×105 5×105 1 8 15 2 9 25 0

数据类型 type 的含义为:

  • type=0,数据无特殊限制。
  • type=1,保证 ∃1≤l′≤r′≤|a|,ali,ri+ali,ri=al′,r′。
  • type=2,保证 ∀r′−l′=ri−li+1,若 al′,r′−1=ali,ri,则必有 ar′≠ali。
  • type=3,保证 ∑ri−li≤105。

其中 al,r 表示字符串 alal+1⋯ar;两个字符串 a+b 的结果为 a 和 b 按顺序拼接的字符串。