/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 466 点
問題文
高橋君は、N 枚のカードを横一列に並べています。カードにはそれぞれ 1 から N までの番号が書かれており、現在は左から順に P_1, P_2, \ldots, P_N の順番で並んでいます。
高橋君は、カードが番号の昇順（左から 1, 2, \ldots, N ）に並んでいる状態を目指しています。並びの乱れ具合を測る指標として、転倒数を用います。
カード列 Q_1, Q_2, \ldots, Q_N の転倒数とは、1 \leq i < j \leq N を満たすすべての組 (i, j) のうち、Q_i > Q_j となる組の個数です。
高橋君は、隣り合う 2 枚のカードを選んで、その 2 枚の位置を入れ替える操作を行うことができます。この操作を最大 K 回まで行うことができ、各回で入れ替える隣り合うペアは自由に選べます（同じペアを複数回選んでもかまいません）。
高橋君が転倒数を最小にするように最適に操作を行ったとき、操作後のカード列の転倒数として達成できる最小値を求めてください。
制約
- 1 \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 が、スペース区切りで与えられる。これは 1 から N までの順列である。
出力
高橋君が最大 K 回の隣接スワップ操作を行った後に達成できる、カード列の転倒数の最小値を 1 行で出力せよ。
入力例 1
5 2 3 1 4 5 2
出力例 1
2
入力例 2
3 100 3 2 1
出力例 2
0
入力例 3
10 5 5 3 8 1 7 2 10 4 6 9
出力例 3
12
Score : 466 pts
Problem Statement
Takahashi has N cards arranged in a horizontal row. Each card has a number from 1 to N written on it, and they are currently arranged in the order P_1, P_2, \ldots, P_N from left to right.
Takahashi aims to arrange the cards in ascending order of their numbers (i.e., 1, 2, \ldots, N from left to right). As a measure of how disordered the arrangement is, he uses the inversion count.
The inversion count of a card sequence Q_1, Q_2, \ldots, Q_N is the number of pairs (i, j) satisfying 1 \leq i < j \leq N such that Q_i > Q_j.
Takahashi can perform an operation where he selects two adjacent cards and swaps their positions. He can perform this operation at most K times, and in each operation, he is free to choose any adjacent pair to swap (the same pair may be chosen multiple times).
When Takahashi performs the operations optimally to minimize the inversion count, find the minimum inversion count of the card sequence that can be achieved after the operations.
Constraints
- 1 \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 inputs are integers
Input
N K P_1 P_2 \ldots P_N
- The first line contains an integer N representing the number of cards and an integer K representing the maximum number of operations, separated by a space.
- The second line contains integers P_1, P_2, \ldots, P_N representing the current order of the cards, separated by spaces. This is a permutation of 1 through N.
Output
Print in one line the minimum inversion count of the card sequence that Takahashi can achieve after performing at most K adjacent swap operations.
Sample Input 1
5 2 3 1 4 5 2
Sample Output 1
2
Sample Input 2
3 100 3 2 1
Sample Output 2
0
Sample Input 3
10 5 5 3 8 1 7 2 10 4 6 9
Sample Output 3
12