#5734. 「OOI 2026 Day1」置换与询问

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2026 Day1 T2 「Перестановки и запросы」 / 「Permutations and Queries」。

给你一个长度为 $n$ 的置换 $p$。长度为 $n$ 的置换是由 $1$ 到 $n$ 这 $n$ 个不同的整数按任意顺序组成的数组。我们定义置换的代价为所有满足 $1 \leq i \leq n$ 的 $(p_i)^i$ 之和（即置换的第 $i$ 个元素的 $i$ 次幂）。因此，置换 $p$ 的代价等于：

现在有 $q$ 个三种类型的询问：

1. 左右翻转：在此操作后，你的置换 $p$ 将被替换为置换 $q$，使得对于所有 $1 \leq i \leq n$，均有 $q_i = p_{n-i+1}$。
2. 数值翻转：在此操作后，你的置换 $p$ 将被替换为置换 $q$，使得对于所有 $1 \leq i \leq n$，均有 $q_i = n - p_i + 1$。
3. 求逆置换：在此操作后，你的置换 $p$ 将被替换为置换 $q$，使得对于所有 $1 \leq i \leq n$，均有 $q_{p_i} = i$。

请注意，每次操作后 $p$ 仍然是一个置换。

在每个询问之后，你需要输出置换的代价。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n, q \leq 100000)$，分别表示置换的长度和询问的数量。

第二行包含 $n$ 个正整数 $p_1, p_2, \dots, p_n$ $(1 \leq p_i \leq n)$，表示置换的元素。保证所有的 $p_i$ 互不相同。

第三行包含 $q$ 个正整数 $b_1, b_2, \dots, b_q$ $(1 \leq b_i \leq 3)$，表示询问的描述。数字 $b_i$ 意味着需要对置换应用的第 $i$ 个修改操作类型为 $b_i$。

输出格式

输出 $q$ 个整数，其中第 $i$ 个整数表示在应用前 $i$ 个询问后，置换代价对 $998244353$ 取模后的余数。

样例 1

输入

5 5
1 2 3 4 5
1 2 3 1 2

输出

65 3413 3413 65 3413

样例 2

输入

5 6
5 3 1 4 2
3 3 1 2 3 1

输出

293 303 3225 215 317 3209

让我们来分析第二个样例。

初始时 $p = [5, 3, 1, 4, 2]$。

第一个询问的类型是 $3$，即求逆置换。操作后置换变为 $[3, 5, 2, 4, 1]$。该置换的代价为 $3^1 + 5^2 + 2^3 + 4^4 + 1^5 = 3 + 25 + 8 + 256 + 1 = 293$。

第二个询问的类型是 $3$，即再次求逆置换。操作后置换变回 $[5, 3, 1, 4, 2]$。该置换的代价为 $5^1 + 3^2 + 1^3 + 4^4 + 2^5 = 5 + 9 + 1 + 256 + 32 = 303$。

第三个询问的类型是 $1$，即左右翻转。操作后置换变为 $[2, 4, 1, 3, 5]$。该置换的代价为 $2^1 + 4^2 + 1^3 + 3^4 + 5^5 = 2 + 16 + 1 + 81 + 3125 = 3225$。

第四个询问的类型是 $2$，即数值翻转。操作后置换变为 $[4, 2, 5, 3, 1]$。该置换的代价为 $4^1 + 2^2 + 5^3 + 3^4 + 1^5 = 4 + 4 + 125 + 81 + 1 = 215$。

第五个询问的类型是 $3$，即求逆置换。操作后置换变为 $[5, 2, 4, 1, 3]$。该置换的代价为 $5^1 + 2^2 + 4^3 + 1^4 + 3^5 = 5 + 4 + 64 + 1 + 243 = 317$。

最后一个询问的类型是 $1$，即左右翻转。操作后置换变为 $[3, 1, 4, 2, 5]$。该置换的代价为 $3^1 + 1^2 + 4^3 + 2^4 + 5^5 = 3 + 1 + 64 + 16 + 3125 = 3209$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。