CF2226F Inversion Invasion

有一个长度为 $n$ 的数组 $a$，初始时对于所有 $1 \le i \le n$ 都有 $a_i = 0$。 对于一个排列 $p$，如果对于每一个 $1 \le i \le n$，至少满足以下两个条件之一，则称该排列是合法的： - $a_i = 0$； - $\gcd(p_i, n) = a_i$。 你需要处理 $q$ 次询问。每次询问给定两个整数 $i$ 和 $x$，你需要将 $a_i$ 赋值为 $x$（具有持久性，即每次是在上一次基础上继续修改）。 保证每次询问时 $a_i = 0$，且 $x$ 一定能整除 $n$。 在每次询问后，输出所有合法排列的逆序对数量之和。由于答案可能很大，请对 $998\,244\,353$ 取模后输出。 $^\text{∗}$ 排列定义：长度为 $m$ 的排列是 $1$ 到 $m$ 的所有整数以任意顺序排列的数组。例如，$[2,3,1,5,4]$ 是一个排列；$[1,2,2]$ 不是，因为 $2$ 出现了两次；$[1,3,4]$ 也不是，因为 $m=3$ 但存在 $4$。 $^\text{†}$ 逆序对定义：对于排列 $p$，如果存在 $ip_j$，则 $(i,j)$ 为一个逆序对。例如排列 $[4, 1, 3, 2]$ 有 $4$ 个逆序对，分别是 $(1,2)$、$(1,3)$、$(1,4)$、$(3,4)$。

每组测试用例包含多个测试数据。第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 每组测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 2 \cdot 10^6$，$1 \le q \le \min(n, 10^6)$），表示数组 $a$ 的长度和询问次数。 接下来的 $q$ 行，每行两个整数 $i$ 和 $x$（$1 \le i \le n$，$1 \le x \le n$）。 保证每次询问时 $a_i = 0$，且 $x$ 能整除 $n$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^6$，所有测试用例中 $q$ 的总和不超过 $10^6$。

对于每组测试用例，输出 $q$ 个整数，依次表示每次询问之后所有合法排列的逆序对数量之和。 由于答案可能很大，每个答案需对 $998\,244\,353$ 取模。

对于第一个测试用例，最初 $a=[0,0,0]$。 第一次询问后，$a=[0,3,0]$。合法排列为 $[1, 3, 2]$ 与 $[2, 3, 1]$，总逆序对数为 $1+2=3$。 第二次询问后，$a=[0,3,3]$。没有合法排列。 由 ChatGPT 5 翻译