AT_arc218_e [ARC218E] Reverse and Reverse

对于一个 $N$ 元排列 $p = (p_1, p_2, \dots, p_N)$（即 $p$ 是 $1,2,\dots,N$ 的一个排列）和正整数 $M$，定义 $f(p, M)$ 为以下问题的答案： > 对 $p$ 进行如下操作 $M$ 次： > > - 选择一个整数 $i$，满足 $1 \le i \le N-1$，将 $(p_1, p_2, \dots, p_i)$ 和 $(p_{i+1}, p_{i+2}, \dots, p_N)$ 分别反转。形式上，将 $p$ 替换为 $(p_i, p_{i-1}, \dots, p_1, p_N, p_{N-1}, \dots, p_{i+1})$。 > > 共存在 $(N-1)^M$ 种操作序列。求所有这些操作序列最终得到的排列的逆序对数量总和，结果对 $998244353$ 取模。 给定一个 $N$ 元排列 $P = (P_1, P_2, \dots, P_N)$。之后需要处理 $Q$ 个询问： - 每次给定一个整数 $x$ $(1 \le x \le N-1)$ 和正整数 $K$，将 $P_x$ 与 $P_{x+1}$ 交换，然后计算 $f(P, K)$。

输入由标准输入给出，格式如下： > $N\ Q$ > $P_1\ P_2\ \dots\ P_N$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 每个询问格式如下： > $x\ K$

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个询问的答案。

### 样例解释 1 对于第一个询问，交换 $P_1$ 和 $P_2$，得到 $P=(3,1,2)$。存在两种操作序列： - 选 $i=1$，$P$ 变为 $(3,2,1)$，逆序对数为 $3$。 - 选 $i=2$，$P$ 变为 $(1,3,2)$，逆序对数为 $1$。 答案为 $3+1=4$。 对于第二个询问，交换 $P_2$ 和 $P_3$，得到 $P=(3,2,1)$。两种方案： - 选 $i=1$，$P=(3,1,2)$，逆序对数为 $2$。 - 选 $i=2$，$P=(2,3,1)$，逆序对数为 $2$。 答案为 $2+2=4$。 ### 数据范围 - $2 \le N \le 2 \times 10^5$ - $1 \le Q \le 2 \times 10^5$ - $P$ 是 $1,2,\dots,N$ 的一个排列。 - $1 \le x \le N-1$ - $1 \le K \le 10^9$ - 输入均为整数。 由 ChatGPT 5 翻译