P5310 [Ynoi2011] A Distant Past

When I was in the 6th grade, I learned Java and wrote a small game. It basically flung my math olympiad teacher’s head to hit frogs. Looks like I already understood mouha and P-head back then. Now I feel I didn’t understand a lot at the time and was just writing randomly. The program was full of if’s, yet I still finished it and even won a first prize in a science and innovation contest (it could add 5 points to the high school entrance exam, definitely not shady!). So I’ve always felt I actually like doing creative things. This will show up later too. In middle school, because I had learned some elementary olympiad math and also some math contest stuff, I felt the classes were plain and wasn’t very interested. I first encountered the informatics olympiad. It felt quite interesting, but I didn’t study it seriously. Our school had OI training, but they taught Pascal. Since I had already learned Java, I naturally thought that language was outdated and trash, so I didn’t really listen. I remember I took a selection test and there was a “chicken and rabbit in the same cage” problem. I wrote a solution using equations and got points deducted. The teacher’s official solution was something like while( a-- ) b++. Then I decided not to go anymore. In the 8th grade I took the NOIP Junior group and only got 120. The second problem was expression evaluation. I spent a long time on it and kept failing, then that was it. After the exam I learned that several classmates were top 10 in the province. They seemed really strong. I was still very competitive back then, so I decided to study OI well and crush them in 9th grade. In 9th grade I got 295 and got crushed by two 8th graders at the time, but I was the highest in 9th grade. Those two kids seem to have gone to Cha Yuan now. Truly legends. Middle school felt quite fun. Although I had to play mind games with a toxic teacher every day, it was still interesting. [Remember to add images. Content: a screenshot of the small game, and the NOIP score.] Since this is Ynoi, not a place for the problem setter to write strange essays, you now need to do a data structure problem:

Little F decides to design a language with a huge character set — the Z language — even if extra characters are sometimes useless. Features of this language: - The character set is extremely large, possibly with $2147483648\ (2^{31})$ distinct characters. - Each word is made of a sequence of pairwise distinct characters. - Characters can be compared for equality and order, so we will use numbers to represent the strange characters in the Z language. - Two words that look completely different can still be the same word because: as long as the positions of the $K$-th largest characters are the same in both words for every $K$, then they are essentially the same word. For example, $\{1, 2, 3, 4, 5\}$ and $\{2, 3, 23, 233, 23333\}$ are the same. (So you can conveniently use the Z language to encrypt information!) Now, Little F plans to apply the Z language to a real task. For example, he opens an algorithm problem on a computer: > Given two strings $A$ and $B$, find how many times $B$ is matched as a substring in $A$. Little F knows this is a basic problem solvable with KMP. However, when implementing Z-KMP for matching in the Z language, he ran into trouble. Can you help him? To verify you really understand what Little F means, he will modify string $B$ many times and ask you. No slacking! See the input and output formats for the operations your program must support.

The first line contains two integers $n, m, q$ ($1 \leq n, m, q \leq 10^5$), the lengths of strings $A$ and $B$, and the number of operations. The second line contains $n$ non-negative integers. The $i$-th is the $i$-th character $A_i$ of string $A$ ($0 \leq A_i \leq 2147483647 = 2^{31}-1$). The third line contains $m$ non-negative integers. The $i$-th is the $i$-th character $B_i$ of string $B$ ($0 \leq B_i \leq 2147483647 = 2^{31}-1$). Then follow $q$ lines. Each line contains two positive integers $x_i, c_i$ ($1 \leq c_i \leq 2147483647 = 2^{31}-1$), meaning the character at position $x_i$ in $B$ is changed from $B_{x_i}$ to $c_i$. The testdata guarantees that at any time, both $A$ and $B$ are valid Z strings that satisfy the above requirements.

After each modification, output the number of times $B$ is Z-matched as a substring in $A$.

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477 (partially uploaded). Sample 1 Explanation: - After the first modification, $\{3, 5, 1\}$ cannot be matched by any substring of $A$. - After the second modification, $\{6, 5, 1\}$ can be matched by every length-$3$ substring of $A$, because $A$ is strictly decreasing and $B$ is also strictly decreasing, so positions of characters with the same ranks coincide. Subtasks: - Subtask $1$ (31 pts): $n, m \leq 100$, $q \leq 1000$. - Subtask $2$ (41 pts): $n, m \leq 1000$, $q \leq 5 \times 10^4$. - Subtask $3$ (78 pts): $n, m, q \leq 10^5$. Translated by ChatGPT 5