/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 466 点
問題文
高橋君は \(N\) 人の生徒が一列に並んでいる列を管理しています。生徒にはそれぞれ \(1\) から \(N\) までの出席番号が付けられており、左から \(i\) 番目の位置には出席番号 \(P_i\) の生徒が立っています。すなわち、\((P_1, P_2, \ldots, P_N)\) は \(1\) から \(N\) の順列です。
高橋君はこの列をできるだけ出席番号順（昇順）に近づけたいと考えています。列の「乱れ度」を、\(i < j\) かつ \(P_i > P_j\) となる組 \((i, j)\) の個数（転倒数）として定義します。
高橋君は以下の操作を ちょうど \(K\) 回 行います：
- 隣り合う \(2\) 人の生徒を選び、位置を入れ替える。すなわち、ある \(i\)（\(1 \leq i \leq N - 1\)）を選んで \(P_i\) と \(P_{i+1}\) を交換する。
\(K\) 回の操作をすべて行った後の列の乱れ度（転倒数）として、あり得る最小の値を求めてください。
なお、同じ位置の組を複数回選んでもよく、一度交換したものを元に戻す操作も許されます。
制約
- \(2 \leq N \leq 2 \times 10^5\)
- \(0 \leq K \leq 10^{18}\)
- \((P_1, P_2, \ldots, P_N)\) は \((1, 2, \ldots, N)\) の順列である
- 入力はすべて整数である
入力
\(N\) \(K\) \(P_1\) \(P_2\) \(\ldots\) \(P_N\)
- \(1\) 行目には、生徒の人数を表す \(N\) と操作回数を表す \(K\) が、スペース区切りで与えられる。
- \(2\) 行目には、初期の並びを表す \(P_1, P_2, \ldots, P_N\) が、スペース区切りで与えられる。
出力
\(K\) 回の操作後の並びの転倒数としてあり得る最小の値を \(1\) 行で出力せよ。
入力例 1
5 3 3 1 4 5 2
出力例 1
1
入力例 2
4 2 1 3 2 4
出力例 2
1
入力例 3
10 15 6 1 8 3 10 2 7 4 9 5
出力例 3
4
入力例 4
30 123456789012 17 3 25 1 29 12 8 21 5 30 14 2 19 27 10 6 23 15 28 4 11 20 7 26 13 9 24 16 22 18
出力例 4
1
入力例 5
2 1000000000000000000 1 2
出力例 5
0
Score : 466 pts
Problem Statement
Takahashi is managing a line of \(N\) students. Each student has a unique student ID from \(1\) to \(N\), and the student standing at the \(i\)-th position from the left has student ID \(P_i\). That is, \((P_1, P_2, \ldots, P_N)\) is a permutation of \((1, 2, \ldots, N)\).
Takahashi wants to make this line as close to student ID order (ascending order) as possible. We define the "disorderliness" of the line as the number of pairs \((i, j)\) such that \(i < j\) and \(P_i > P_j\) (the number of inversions).
Takahashi will perform the following operation exactly \(K\) times:
- Choose two adjacent students and swap their positions. That is, choose some \(i\) (\(1 \leq i \leq N - 1\)) and swap \(P_i\) and \(P_{i+1}\).
Find the minimum possible disorderliness (number of inversions) of the line after performing all \(K\) operations.
Note that the same pair of adjacent positions may be chosen multiple times, and operations that undo previous swaps are also allowed.
Constraints
- \(2 \leq N \leq 2 \times 10^5\)
- \(0 \leq K \leq 10^{18}\)
- \((P_1, P_2, \ldots, P_N)\) is a permutation of \((1, 2, \ldots, N)\)
- All input values are integers.
Input
\(N\) \(K\) \(P_1\) \(P_2\) \(\ldots\) \(P_N\)
- The first line contains \(N\), the number of students, and \(K\), the number of operations, separated by a space.
- The second line contains \(P_1, P_2, \ldots, P_N\), representing the initial arrangement, separated by spaces.
Output
Print the minimum possible number of inversions of the arrangement after \(K\) operations in a single line.
Sample Input 1
5 3 3 1 4 5 2
Sample Output 1
1
Sample Input 2
4 2 1 3 2 4
Sample Output 2
1
Sample Input 3
10 15 6 1 8 3 10 2 7 4 9 5
Sample Output 3
4
Sample Input 4
30 123456789012 17 3 25 1 29 12 8 21 5 30 14 2 19 27 10 6 23 15 28 4 11 20 7 26 13 9 24 16 22 18
Sample Output 4
1
Sample Input 5
2 1000000000000000000 1 2
Sample Output 5
0