E. Reverse and Reverse

Reverse and Reverse

AtCoder

⌀ 2705

Reverse and ReverseAI (CI翻译)

Problem Statement

For a permutation $p=(p_1,p_2,\dots,p_N)$ of $(1,2,\dots,N)$ and a positive integer $M$ , let $f(p,M)$ denote the answer to the following problem.

Perform the following operation $M$ times on $p$ .

Choose an integer $i$ with $1 \le i \le N-1$ , and reverse each of $(p_1,p_2,\dots,p_i)$ and $(p_{i+1},p_{i+2},\dots,p_N)$ . Formally, replace $p$ with $(p_i,p_{i-1},\dots,p_1,p_N,p_{N-1},\dots,p_{i+1})$ .

There are $(N-1)^M$ possible sequences of operations. Find the sum, modulo $998244353$ , of "the number of inversions of $p$ after $M$ operations" over all such sequences.

You are given a permutation $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$ . Process the following query $Q$ times.

You are given an integer $x$ with $1 \le x \le N-1$ and a positive integer $K$ . Swap $P_x$ and $P_{x+1}$ . Then, find $f(P,K)$ .

Constraints

$2 \le N \le 2 \times 10^5$
$1 \le Q \le 2 \times 10^5$
$P$ is a permutation of $(1,2,\dots,N)$ .
$1 \le x \le N-1$
$1 \le K \le 10^9$
All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
P_1\ P_2\ \dots\ P_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

x K

Output

Output $Q$ lines. The $i$ -th line should contain the answer to $\mathrm{query}_i$ .

{"titleZh":"反转与反转","bodyZh":"## 题目描述\n\n对于排列 $p=(p_1,p_2,\\dots,p_N)$ （由 $(1,2,\\dots,N)$ 构成）和正整数 $M$ ，令 $f(p,M)$ 表示以下问题的答案。\n\n> 对 $p$ 执行以下操作 $M$ 次。\n>\n> - 选择一个满足 $1 \\le i \\le N-1$ 的整数 $i$ ，然后分别反转 $(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>\n> 一共有 $(N-1)^M$ 种可能的操作序列。求所有这些操作序列中“执行 $M$ 次操作后 $p$ 的逆序对数”之和，结果对 $998244353$ 取模。\n\n给定一个由 $(1,2,\\dots,N)$ 构成的排列 $P=(P_1,P_2,\\dots,P_N)$ 。请处理以下 $Q$ 次查询。\n\n- 给定一个满足 $1 \\le x \\le N-1$ 的整数 $x$ 和一个正整数 $K$ 。交换 $P_x$ 与 $P_{x+1}$ ，然后求 $f(P,K)$ 。\n\n## 约束条件\n\n- $2 \\le N \\le 2 \\times 10^5$ \n- $1 \\le Q \\le 2 \\times 10^5$ \n- $P$ 是 $(1,2,\\dots,N)$ 的一个排列。\n- $1 \\le x \\le N-1$ \n- $1 \\le K \\le 10^9$ \n- 所有输入值均为整数。\n\n## 输入格式\n\n输入从标准输入按以下格式给出：\n\n\nN Q\nP_1\\ P_2\\ \\dots\\ P_N\n\\mathrm{query}_1\n\\mathrm{query}_2\n\\vdots\n\\mathrm{query}_Q\n`\n\n每次查询的格式如下：\n\n`\nx K\n\n\n## 输出格式\n\n输出 $Q$ 行。第 $i$ 行应包含对第 $\mathrm{query}_i$ 次查询的答案。"}AI (CI翻译)

样例

Input #1

Output #1

4
4

For the first query, swapping $P_1$ and $P_2$ gives $P=(3,1,2)$. There are two possible sequences of operations as follows: - Choose $i = 1$. $P$ becomes $(3,2,1)$. The number of inversions is $3$. - Choose $i = 2$. $P$ becomes $(1,3,2)$. The number of inversions is $1$. Thus, the answer is $3+1=4$. For the second query, swapping $P_2$ and $P_3$ gives $P=(3,2,1)$. There are two possible sequences of operations as follows: - Choose $i = 1$. $P$ becomes $(3,1,2)$. The number of inversions is $2$. - Choose $i = 2$. $P$ becomes $(2,3,1)$. The number of inversions is $2$. Thus, the answer is $2+2=4$.

Input #2

Output #2

Input #3

10 7
7 9 3 10 5 2 4 6 8 1
2 29
1 86
3 30
8 64
1 24
1 9
5 55

Output #3

题目信息

题号

arc218_e

所属比赛

AtCoder Regular Contest 218

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。