P16177 [ICPC 2014 NAIPC] Fantastic Problem

世界著名的问题编写者 Andrew 终于决定退休了。然而，他首先希望推出最后一部杰作，以巩固他的传奇地位，并让全世界的参赛者惊叹不已。作为他最喜爱的学生，他请你在他将题目提交给 ICFP（国际精彩问题委员会）之前，帮他校对一下。 这道题被证明是一个相当复杂的数论问题，但你最终还是得出了一个解法……结果却发现它无法通过他的数据。在浪费了数小时调试你的代码之后，你意识到你的代码是正确的——而是数据无效！Andrew 的高龄似乎真的让他力不从心了。 在他的问题中，你得到了一个包含 $n$ 个整数的序列 $V_{1\dots n}$，并且有一个重要的保证：在每一个长度为 $k$ 的连续整数区间（即某个起始下标 $i$ 对应的 $V_i\dots V_{i+k-1}$）内，任意两个整数都是互质的（两个整数互质意味着它们除了 1 之外没有其他公因数）。然而，Andrew 的数据中并未满足这一条件，导致你的程序崩溃了！ 为了帮助你敬爱的导师，你统计出有多少个长度为 $k$ 的区间不满足他问题描述中的承诺。不幸的是，你的工作还没有结束。由于难以修复他的数据，Andrew 进行了 $m$ 次顺序更新，每次更新涉及选择数列中的某个位置 $a$，并将其值改为某个值 $b$。在每次更改之后，他都想知道他的新序列中包含多少个不合法的长度为 $k$ 的区间。似乎这还不够，在第 $m$ 次更新之后，Andrew 认为数据已经足够好了，并希望你用最终的整数序列来解决他的问题！他的问题陈述如下： > 给定一个整数序列，计算它们的和。

输入中有多个测试用例。每个测试用例的第一行包含三个整数 $n$（$1 \leq n \leq 100{,}000$）、$k$（$1 \leq k \leq n$）和 $m$（$1 \leq m \leq 100{,}000$），其中 $n$ 是 Andrew 列表的大小，$k$ 是相关连续区间的大小，$m$ 是 Andrew 进行的更改次数。接下来的 $n$ 行，每行包含一个整数 $v$（$1 \leq v \leq 100{,}000$），表示 Andrew 输入中的一个值。这些 $v$ 按它们在 Andrew 列表中出现的顺序给出。接下来的 $m$ 行，每行包含两个整数 $a$（$1 \leq a \leq n$）和 $b$（$1 \leq b \leq 100{,}000$），表示 Andrew 将值 $V_a$ 更改为 $b$。输入以一行三个 0 结束。测试数据大小约 17 MB。

对于每个测试用例，输出 $m+2$ 个整数。第一个整数应为 Andrew 原始列表中不满足两两互质约束的长度为 $k$ 的区间数量。接下来的 $m$ 个整数应依次为在 Andrew 进行 $m$ 次更改后，每次更改后不满足约束的区间数量。最后一个整数应为最终列表中所有数字的和。每个整数输出在自己的行上，不要包含空格。输出之间不要打印空行。

翻译由 DeepSeek V3.2 完成