/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
(1,2,\dots,N) の順列 p=(p_1,p_2,\dots,p_N) と正整数 M に対して、以下の問題の答えを f(p,M) と置きます。
p に対して以下の操作を M 回行います。
- 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-1)^M 通りありますが、その全てに対する「M 回の操作終了後の p の転倒数」の総和を 998244353 で割った余りを求めてください。
(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) が与えられます。以下のクエリを Q 回処理してください。
- 1 \le x \le N-1 を満たす整数 x と正整数 K が与えられる。P_x,P_{x+1} を swap する。その後、f(P,K) を求めよ。
制約
- 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
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q
P_1\ P_2\ \dots\ P_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各クエリは以下の形式で与えられる。
x K
出力
Q 行出力せよ。i 行目には \mathrm{query}_i の答えを出力せよ。
入力例 1
3 2 1 3 2 1 1 2 1
出力例 1
4 4
1 番目のクエリについて、P_1,P_2 を swap することで P=(3,1,2) となります。操作列は 2 通りあり、それぞれ以下のようになります。
- i = 1 を選ぶ。P=(3,2,1) となる。転倒数は 3 である。
- i = 2 を選ぶ。P=(1,3,2) となる。転倒数は 1 である。
よって答えは 3+1=4 です。
2 番目のクエリについて、P_2,P_3 を swap することで P=(3,2,1) となります。操作列は 2 通りあり、それぞれ以下のようになります。
- i = 1 を選ぶ。P=(3,1,2) となる。転倒数は 2 である。
- i = 2 を選ぶ。P=(2,3,1) となる。転倒数は 2 である。
よって答えは 2+2=4 です。
入力例 2
4 4 3 2 4 1 2 1 2 2 3 3 1 4
出力例 2
11 28 67 242
入力例 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
出力例 3
29362950 633265500 847469581 741165544 385334408 653522086 169485402
Score : 800 points
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.
Sample Input 1
3 2 1 3 2 1 1 2 1
Sample 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.
Sample Input 2
4 4 3 2 4 1 2 1 2 2 3 3 1 4
Sample Output 2
11 28 67 242
Sample 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
Sample Output 3
29362950 633265500 847469581 741165544 385334408 653522086 169485402