P8992 [Peking University Training 2021] Poker Card Comparison.

CTT2021 D3T3

Little $Z$ and Little $A$ are playing a poker card comparison game. The rules of their game are as follows: - Before the game starts, the system deals a pile of hand cards to Little $Z$ and a pile of hand cards to Little $A$ (the numbers of cards in the two piles may be different). Each card has a lowercase letter written on it. - In each round of the game, Little $Z$ and Little $A$ simultaneously flip the first card on the **top of their piles**. If the two flipped cards are different, then the player whose card corresponds to the **smaller** lowercase letter wins. If the two flipped cards are the same, they put the flipped cards into the **bottom of their piles** and continue the game until one side wins. In fact, the system deals cards from a huge deck. Specifically, suppose the deck has $n$ cards, which are $a_1,a_2,\cdots,a_n$. Then the system randomly selects cards from the $l$-th card to the $r$-th card to deal to a player. In other words, from the **top of the pile to the bottom of the pile**, the cards are $a_l,a_{l+1},\cdots,a_r$. Now Little $Z$ and Little $A$ will play a total of $q$ games. Little $Z$ learns in some way that, in the $i$-th game, the cards dealt to Little $A$ are $a_{l_i},a_{l_i+1},\cdots,a_{r_i}$. Little $Z$ wants to know how many possible hand card piles he could have that would allow him to beat Little $A$. Two hand card piles are considered different if and only if the numbers of cards in the two piles are different, or there exists a position $d$ such that the cards at distance $d$ from the top of the piles are different.

The first line contains a string $a$ consisting only of lowercase letters. The second line contains a positive integer $q$ and an integer $type$, where $type$ indicates the data type. The next $q$ lines each contain two integers $l_i$ and $r_i$ on line $i$.

Output $q$ lines. Each line contains an integer indicating how many possible hand card piles Little $Z$ could have that would allow him to beat Little $A$.

For all testdata, it holds that $1\le l_i\le r_i\le |a| \le 5\times 10^5$, $1\le q \le 5\times 10^5$. | Subtask | Score | $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$ | The meaning of data type $type$ is as follows: - $type=0$: The data has no special restrictions. - $type=1$: It is guaranteed that $\exists 1\le l'\le r'\le |a|$, $a_{l_i,r_i}+a_{l_i,r_i}=a_{l',r'}$. - $type=2$: It is guaranteed that $\forall r'-l'=r_i-l_i+1$, if $a_{l',r'-1}=a_{l_i,r_i}$, then it must hold that $a_{r'}\neq a_{l_i}$. - $type=3$: It is guaranteed that $\sum r_i-l_i \le 10^5$. Here $a_{l,r}$ denotes the string $a_la_{l+1}\cdots a_r$. The result of concatenating two strings $a+b$ is the string obtained by appending $b$ after $a$ in order. Translated by ChatGPT 5