P15080 [ICPC 2024 Chengdu R] Good Partitions

Lawliet has a sequence of numbers of length $n$, denoted as $a_1, a_2, \ldots, a_n$, and he wants to determine how many good partitions exist. A partition size $k$ is considered a good partition size if it satisfies $1 \leq k \leq n$ and, after dividing the sequence $a$ into parts by partition size, each resulting sub-sequence is non-decreasing. The partitioning method is as follows: - The sequence $a$ is divided into $\lceil \frac{n}{k} \rceil$ parts. - For the $i$-th part ($1 \leq i \leq \lceil \frac{n}{k} \rceil - 1$), the elements are $a_{(i - 1) \times k + 1}, a_{(i - 1) \times k + 2}, \ldots, a_{i \times k}$. - For the $\lceil \frac{n}{k} \rceil$-th part, the elements are $a_{(\lceil \frac{n}{k} \rceil - 1) \times k + 1}, \ldots, a_n$. Note that the length of the last part may be less than $k$. Lawliet finds this problem too simple, so he will make $q$ modifications. Each modification provides two positive integers $p$ and $v$, indicating that the value of $a_p$ will be changed to $v$. Your task is to help Lawliet calculate the number of good partition sizes before any modifications and after each modification.

The first line contains an integer $T$ ($1\le T \le 10$), representing the number of test cases. For each test case, the first line contains two integers $n$ ($1 \le n \le 2 \cdot 10^5$) and $q$ ($1 \le q \le 2 \cdot 10^5$), representing the length of the sequence and the number of modifications. The second line contains $n$ integers, representing the sequence $a_1, a_2, \ldots, a_n$ ($1\le a_i\le 2\cdot 10^9$). The following $q$ lines each contain two integers $p$ ($1 \le p \le n$) and $v$ ($1 \le v \le 2 \cdot 10^9$), indicating that the element at the $p$-th position in the sequence will be modified to $v$. It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $2\cdot 10^5$, respectively.

For each test case, output $q + 1$ lines, representing the number of good partition sizes before any modifications and after each modification.

Initially, the only good partition size is $k = 1$. After the first modification, the sequence becomes $[4, 5, 2, 6, 1]$. Both $k = 1$ and $k = 2$ are good partition sizes. After the second modification, the sequence becomes $[4, 5, 5, 6, 1]$. The good partition sizes are $k = 1$, $k = 2$, and $k = 4$.