UOJ Logo Universal Online Judge

UOJ

#717. 【北大集训2021】扑克比大小

附件下载 统计

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

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

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

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

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

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

输入格式

从标准输入读入数据。

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

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

接下来 $q$ 行,第 $i$ 行包含两个整数 $l_i$ 和 $r_i$。

输出格式

输出到标准输出。

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

样例

input

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

output

4
7
6
2
8

样例二、三

见附件下载。

数据范围与提示

对于所有数据,满足 $1\le l_i\le r_i\le |a| \le 5 \times 10^{5}$,$1\le q \le 5 \times 10^{5}$。

子任务 得分 $n\le$ $q\le$ $type$
$1$ $3$ $10^{2}$ $10^{2}$ $0$
$2$ $3$ $500$ $2000$
$3$ $4$ $2000$
$4$ $5$ $2 \times 10^{4}$
$5$ $13$ $10^{5}$ $10^{5}$ $3$
$6$ $17$ $0$
$7$ $15$ $5 \times 10^{5}$ $5 \times 10^{5}$ $1$
$8$ $15$ $2$
$9$ $25$ $0$

数据类型 $type$ 的含义为:

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

  • $type=1$,保证 $\exists 1\le l'\le r'\le |a|$,$a_{l_i,r_i}+a_{l_i,r_i}=a_{l',r'}$。

  • $type=2$,保证 $\forall r'-l'=r_i-l_i+1$,若 $a_{l',r'-1}=a_{l_i,r_i}$,则必有 $a_{r'}\neq a_{l_i}$。

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

其中 $a_{l,r}$ 表示字符串 $a_la_{l+1}\cdots a_r$;两个字符串 $a+b$ 的结果为 $a$ 和 $b$ 按顺序拼接的字符串。

hack

hack 数据必须保证 $type=0$。

时间限制:6s$\texttt{12s}$

空间限制:$\texttt{2GB}$