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

CTT2021 D3T3

小 $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$。

对于所有数据，满足 $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$ | $2,000$ | $0$ | | $3$ | $4$ | $2,000$ | $2,000$ | $0$ | | $4$ | $5$ | $2\times 10^4$ | $2,000$ | $0$ | | $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 $ | $5\times 10^5$ | $5\times 10^5$ | $2$ | | $9$ | $25$ | $5\times 10^5$ | $5\times 10^5$ | $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$ 按顺序拼接的字符串。