{"problem":{"name":"[北大集训 2021] 扑克比大小","description":{"content":"小 $Z$ 和小 $A$ 在玩扑克比大小。 他们玩的扑克比大小规则如下： - 在游戏开始前，系统会给小 $Z$ 和小 $A$ 各发一堆手牌（两堆牌数量可能不相同），其中每张牌上写有一个小写字母。 - 在游戏的每一轮，小 $Z$ 和小 $A$ 同时翻开**牌堆顶**的第一张牌，若两人翻开的牌不同，则牌上对应小写字母**更小**的那一方获胜；若两人翻开的牌相同，则他们会将翻开的牌塞入**牌堆底*","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":2097152},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8992"},"statements":[{"statement_type":"Markdown","content":"小 $Z$ 和小 $A$ 在玩扑克比大小。\n\n他们玩的扑克比大小规则如下：\n\n- 在游戏开始前，系统会给小 $Z$ 和小 $A$ 各发一堆手牌（两堆牌数量可能不相同），其中每张牌上写有一个小写字母。\n\n- 在游戏的每一轮，小 $Z$ 和小 $A$ 同时翻开**牌堆顶**的第一张牌，若两人翻开的牌不同，则牌上对应小写字母**更小**的那一方获胜；若两人翻开的牌相同，则他们会将翻开的牌塞入**牌堆底**，继续游戏，直到某方获胜为止。\n\n而系统实际上是从一个巨大的牌库里面发牌的，具体来说，假设牌库共有 $n$ 张牌，分别是 $a_1,a_2,\\cdots,a_n$，则系统会随机选择第 $l$ 张到第 $r$ 张牌发给玩家，换言之，玩家**从牌堆顶到牌堆底**的牌分别是 $a_l,a_{l+1},\\cdots,a_r$。\n\n现在小 $Z$ 和小 $A$ 一共要进行 $q$ 轮游戏，并且小 $Z$ 通过某种方式得知了系统在第 $i$ 轮发给小 $A$ 的牌为 $a_{l_i},a_{l_i+1},\\cdots,a_{r_i}$，小 $Z$ 想知道他一共有多少种可能的手牌能赢小 $A$。两堆手牌视为不同当且仅当两堆手牌数量不同，或存在一个位置 $d$ 使得两堆手牌中距离堆顶为 $d$ 的牌不同。\n\n## Input\n\n输入的第一行包含一个只包含小写字母的字符串 $a$ 。\n\n输入的第二行包含一个正整数 $q$ 和一个整数 $type$，其中 $type$ 表示数据类型。\n\n接下来 $q$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$。\n\n## Output\n\n输出 $q$ 行，每行一个整数表示小 $Z$ 有多少种可能的手牌能赢小 $A$。\n\n[samples]\n\n## Background\n\nCTT2021 D3T3\n\n## Note\n\n对于所有数据，满足 $1\\le l_i\\le r_i\\le |a| \\le 5\\times 10^5$，$1\\le q \\le 5\\times 10^5$。\n\n| 子任务 | 得分  |     $n\\le$     |     $q\\le$     | $type$ |\n| :----: | :---: | :------------: | :------------: | :----: |\n|  $1$   |  $3$  |     $10^2$     |     $10^2$     |  $0$   |\n|  $2$   |  $3 $  |     $500$      |    $2,000$     |  $0$   |\n|  $3$   |  $4$  |    $2,000$     |    $2,000$     |  $0$   |\n|  $4$   |  $5$  | $2\\times 10^4$ |    $2,000$     |  $0$   |\n|  $5$   | $13$  |     $10^5$     |     $10^5$     |  $3$   |\n|  $6$   | $17$  |     $10^5$     |     $10^5$     |  $0$   |\n|  $7$   | $15$  | $5\\times 10^5$ | $5\\times 10^5$ |  $1$   |\n|  $8$   | $15 $ | $5\\times 10^5$ | $5\\times 10^5$ |  $2$   |\n|  $9$   | $25$  | $5\\times 10^5$ | $5\\times 10^5$ |  $0$   |\n\n数据类型 $type$ 的含义为：\n\n- $type=0$，数据无特殊限制。\n\n- $type=1$，保证 $\\exists 1\\le l'\\le r'\\le |a|$，$a_{l_i,r_i}+a_{l_i,r_i}=a_{l',r'}$。\n\n- $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}$。\n\n- $type=3$，保证 $\\sum r_i-l_i \\le 10^5$。\n\n其中 $a_{l,r}$ 表示字符串 $a_la_{l+1}\\cdots a_r$；两个字符串 $a+b$ 的结果为 $a$ 和 $b$ 按顺序拼接的字符串。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8992","tags":["2021","O2优化","CTT（清华集训/北大集训）"],"sample_group":[["abbab\n5 0\n1 3\n2 4\n3 5\n1 4\n2 5\n","4\n7\n6\n2\n8\n"]],"created_at":"2026-03-03 11:09:25"}}