QOJ.ac

QOJ

Time Limit: 8 s Memory Limit: 2048 MB Total points: 100
[+5]

# 3277. 扑克比大小

Statistics

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 行包含两个整数 liri

输出格式

输出到标准输出。

输出 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

见下发文件。

数据范围与提示

对于所有数据,满足 1liri|a|5×1051q5×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,保证 1lr|a|ali,ri+ali,ri=al,r

  • type=2,保证 rl=rili+1,若 al,r1=ali,ri,则必有 arali

  • type=3,保证 rili105

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