【北大集训2021】扑克比大小 - 题目

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

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

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

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

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

输入格式

从标准输入读入数据。

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

输入的第二行包含一个正整数 $q$ 和一个整数 $t y p e$ ，其中 $t y p e$ 表示数据类型。

接下来 $q$ 行，第 $i$ 行包含两个整数 $l_{i}$ 和 $r_{i}$ 。

输出格式

输出到标准输出。

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

样例

input

output

样例二、三

见附件下载。

数据范围与提示

对于所有数据，满足 $1 \leq l_{i} \leq r_{i} \leq | a | \leq 5 \times 10^{5}$ ， $1 \leq q \leq 5 \times 10^{5}$ 。

子任务	得分	$n \leq$	$q \leq$	$t y p e$
$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$	$10^{5}$	$10^{5}$	$0$
$7$	$15$	$5 \times 10^{5}$	$5 \times 10^{5}$	$1$
$8$	$15$			$2$
$9$	$25$			$0$

数据类型 $t y p e$ 的含义为：

$t y p e = 0$ ，数据无特殊限制。
$t y p e = 1$ ，保证 $\exists 1 \leq l^{'} \leq r^{'} \leq | a |$ ， $a_{l_{i}, r_{i}} + a_{l_{i}, r_{i}} = a_{l^{'}, r^{'}}$ 。
$t y p e = 2$ ，保证 $\forall r^{'} - l^{'} = r_{i} - l_{i} + 1$ ，若 $a_{l^{'}, r^{'} - 1} = a_{l_{i}, r_{i}}$ ，则必有 $a_{r^{'}} \neq a_{l_{i}}$ 。
$t y p e = 3$ ，保证 $\sum r_{i} - l_{i} \leq 10^{5}$ 。

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

hack

hack 数据必须保证 $t y p e = 0$ 。

时间限制：6s $12s$

空间限制： $2GB$

Universal Online Judge

UOJ

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