#P8992. [北大集训 2021] 扑克比大小

[北大集训 2021] 扑克比大小

题目背景

CTT2021 D3T3

题目描述

ZZ 和小 AA 在玩扑克比大小。

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

  • 在游戏开始前,系统会给小 ZZ 和小 AA 各发一堆手牌(两堆牌数量可能不相同),其中每张牌上写有一个小写字母。

  • 在游戏的每一轮,小 ZZ 和小 AA 同时翻开牌堆顶的第一张牌,若两人翻开的牌不同,则牌上对应小写字母更小的那一方获胜;若两人翻开的牌相同,则他们会将翻开的牌塞入牌堆底,继续游戏,直到某方获胜为止。

而系统实际上是从一个巨大的牌库里面发牌的,具体来说,假设牌库共有 nn 张牌,分别是 a1,a2,,ana_1,a_2,\cdots,a_n,则系统会随机选择第 ll 张到第 rr 张牌发给玩家,换言之,玩家从牌堆顶到牌堆底的牌分别是 al,al+1,,ara_l,a_{l+1},\cdots,a_r

现在小 ZZ 和小 AA 一共要进行 qq 轮游戏,并且小 ZZ 通过某种方式得知了系统在第 ii 轮发给小 AA 的牌为 ali,ali+1,,aria_{l_i},a_{l_i+1},\cdots,a_{r_i},小 ZZ 想知道他一共有多少种可能的手牌能赢小 AA。两堆手牌视为不同当且仅当两堆手牌数量不同,或存在一个位置 dd 使得两堆手牌中距离堆顶为 dd 的牌不同。

输入格式

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

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

接下来 qq 行,第 ii 行包含两个整数 lil_irir_i

输出格式

输出 qq 行,每行一个整数表示小 ZZ 有多少种可能的手牌能赢小 AA

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

4
7
6
2
8

提示

对于所有数据,满足 1liria5×1051\le l_i\le r_i\le |a| \le 5\times 10^51q5×1051\le q \le 5\times 10^5

子任务 得分 nn\le qq\le typetype
11 33 10210^2 00
22 33 500500 2,0002,000
33 44 2,0002,000
44 55 2×1042\times 10^4
55 1313 10510^5 33
66 1717 00
77 1515 5×1055\times 10^5 11
88 1515 22
99 2525 00

数据类型 typetype 的含义为:

  • type=0type=0,数据无特殊限制。

  • type=1type=1,保证 1lra\exists 1\le l'\le r'\le |a|ali,ri+ali,ri=al,ra_{l_i,r_i}+a_{l_i,r_i}=a_{l',r'}

  • type=2type=2,保证 rl=rili+1\forall r'-l'=r_i-l_i+1,若 al,r1=ali,ria_{l',r'-1}=a_{l_i,r_i},则必有 aralia_{r'}\neq a_{l_i}

  • type=3type=3,保证 rili105\sum r_i-l_i \le 10^5

其中 al,ra_{l,r} 表示字符串 alal+1ara_la_{l+1}\cdots a_r;两个字符串 a+ba+b 的结果为 aabb 按顺序拼接的字符串。