P4036 [JSOI2008] Martians

Martians have recently been studying an operation: finding the common prefix of two suffixes of a string. For example, consider this string: madamimadam. We label its characters as follows: ``` 序号 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m ``` Now, Martians define a function $LCQ(x, y)$, which means: the length of the common prefix between the substring starting at the $x$-th character and the substring starting at the $y$-th character of the string. For example, $LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0$. In the process of studying the $LCQ$ function, Martians found a connection: if you sort all suffixes of the string, you can quickly compute the value of $LCQ$; likewise, if you know the values of $LCQ$, you can quickly sort the suffixes of the string. Although Martians cleverly discovered a fast algorithm for computing $LCQ$, the unyielding Earthlings posed a new challenge: while computing $LCQ$, the string itself may change. Specifically, you may change the value of a character in the string, or insert a character at some position in the string. The Earthlings want to test whether Martians can still compute $LCQ$ quickly under such a complex scenario.

The first line gives the initial string. The second line is a non-negative integer $M$, the number of operations. The next M lines each describe one operation. There are 3 types of operations: 1. Query. Syntax: $Q$ $x$ $y$, where $x$, $y$ are positive integers. Function: compute $LCQ(x, y)$. Constraint: $1 \leq x, y \leq$ current string length. 2. Modify. Syntax: $R$ $x$ $d$, where $x$ is a positive integer and $d$ is a character. Function: replace the $x$-th character of the string with $d$. Constraint: $x$ does not exceed the current string length. 3. Insert. Syntax: $I$ $x$ $d$, where $x$ is a non-negative integer and $d$ is a character. Function: insert character $d$ after the $x$-th character of the string; if $x=0$, insert at the beginning of the string. Constraint: $x$ does not exceed the current string length.

For each query operation in the input, output the corresponding answer, one per line.

1. All strings always consist of lowercase letters only. 2. $M\leq150,000$ 3. The string length $L$ always satisfies $L\leq100,000$. 4. The number of query operations does not exceed $10,000$. For testdata 1 and 2, the string length never exceeds $1,000$. For testdata 3, 4, and 5, there are no insert operations. Translated by ChatGPT 5