Background

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:

Problem Description

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.

Input Format

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.

Output Format

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

5 3 2
11 7 5 3 2
3 2 1
2 5
1 6

0
3

Hint

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