P15080 [ICPC 2024 Chengdu R] Good Partitions

Lawliet 拥有一个长度为 $n$ 的数字序列 $a_1, a_2, \ldots, a_n$，他希望知道「好数字」的个数。 定义一个整数 $k$ 是「好数字」，如果它满足以下条件： - $1 \leq k \leq n$； - 将序列 $a$ 依据 $k$ 按照以下划分方法分成若干份后，每一份序列都是单调不降的。 划分方法为： - 将序列 $a$ 分成 $\lceil \frac{n}{k} \rceil$ 份； - 对于第 $i$ 份（$1 \leq i \leq \lceil \frac{n}{k} \rceil - 1$），包含的元素是 $a_{(i - 1) \times k + 1}, a_{(i - 1) \times k + 2}, \ldots, a_{i \times k}$； - 对于第 $\lceil \frac{n}{k} \rceil$ 份，包含的元素是 $a_{(\lceil \frac{n}{k} \rceil - 1) \times k + 1}, \ldots, a_n$。 Lawliet 认为这个问题太过简单了，于是他会进行 $q$ 次修改，每次修改会给出两个正整数 $p$ 和 $v$，然后将 $a_p$ 的数值修改为 $v$。 Lawliet 需要你帮助计算，对于未进行任何修改前以及序列 $a$ 每次修改后，满足上述条件的「好数字」的个数。

第一行包含一个整数 $t$（$1\le t\le 10$），代表测试组数。 对于每组测试数据，第一行包含两个整数 $n$（$1 \le n \le 2 \cdot 10^5$）和 $q$（$1 \le q \le 2 \cdot 10^5$），分别表示序列的长度和修改次数。 第二行包含 $n$ 个整数，表示序列 $a_1, a_2, \ldots, a_n$（$1\le a_i\le 2\cdot 10^9$）。 接下来的 $q$ 行，每行包含两个整数 $p$（$1 \le p \le n$）和 $v$（$1 \le v \le 2 \cdot 10^9$），表示将序列中的第 $p$ 个位置的元素修改为 $v$。 单个测试点中 $n$ 之和与 $q$ 之和均不超过 $2\cdot 10^5$。

对于每组测试数据，输出 $q + 1$ 行，分别代表未进行任何修改前以及序列 $a$ 每次修改后，序列中的「好数字」的个数。

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$.