/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の球が左右一列に並んでいます。 左から i 番目の球の色は色 C_i であり、整数 X_i が書かれています。
高橋君の目標は球を左から右に見た時に書かれている数が非減少になるように球を並べ替えることです。 言い換えれば、高橋君の目標は、任意の 1\leq i\leq N-1 について、左から i+1 番目の球に書かれている数 が左から i 番目に書かれている数以上であるようにすることです。
高橋君は目標を達成するために、次の操作を好きなだけ（ 0 回でも良い ）繰り返すことができます。
1\leq i\leq N-1 をみたす整数 i を選ぶ。
左から i 番目の球と i+1 番目の球の色が異なっているならば、コストを 1 支払う。 （色が等しいならばコストを支払う必要は無い。）
左から i 番目の球と i+1 番目の球を入れ替える。
高橋君が目標を達成するために支払う必要のあるコストの最小値を求めてください。
制約
- 2 \leq N \leq 3\times 10^5
- 1\leq C_i\leq N
- 1\leq X_i\leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N C_1 C_2 \ldots C_N X_1 X_2 \ldots X_N
出力
高橋君が支払う必要のあるコストの最小値を整数で出力せよ。
入力例 1
5 1 5 2 2 1 3 2 1 2 1
出力例 1
6
球の情報を (色, 整数) で表すとします。 最初の状態は (1,3), (5,2), (2,1), (2,2), (1,1) です。 例えば、高橋君は次のように操作を行うことができます。
- 左から 1 番目の球 (色 1) と 2 番目の球 (色 5) を入れ替える。 球は左から (5,2), (1,3), (2,1), (2,2), (1,1) となる。
- 左から 2 番目の球 (色 1) と 3 番目の球 (色 2) を入れ替える。 球は左から (5,2), (2,1), (1,3), (2,2), (1,1) となる。
- 左から 3 番目の球 (色 1) と 4 番目の球 (色 2) を入れ替える。 球は左から (5,2), (2,1), (2,2), (1,3), (1,1) となる。
- 左から 4 番目の球 (色 1) と 5 番目の球 (色 1) を入れ替える。 球は左から (5,2), (2,1), (2,2), (1,1), (1,3) となる。
- 左から 3 番目の球 (色 2) と 4 番目の球 (色 1) を入れ替える。 球は左から (5,2), (2,1), (1,1), (2,2), (1,3) となる。
- 左から 1 番目の球 (色 5) と 2 番目の球 (色 2) を入れ替える。 球は左から (2,1), (5,2), (1,1), (2,2), (1,3) となる。
- 左から 2 番目の球 (色 5) と 3 番目の球 (色 1) を入れ替える。 球は左から (2,1), (1,1), (5,2), (2,2), (1,3) となる。
最後の操作の後で球に書かれている数は左から順に 1,1,2,2,3 となっているため、高橋君は目的を達成しています。
1,2,3,5,6,7 回目の操作にコストが 1 ずつかかるため、
このとき合計でコストは 6 かかり、このときが最小となります。
4 回目の操作では、入れ替えた球の色がともに色 1 であるためコストがかからないことに注意してください。
入力例 2
3 1 1 1 3 2 1
出力例 2
0
すべての球の色は同じであるため、球の入れ替えにコストがかかることはありません。
入力例 3
3 3 1 2 1 1 2
出力例 3
0
高橋君は一度も操作を行わずとも、目的を達成できています。
Score : 500 points
Problem Statement
There are N balls arranged from left to right. The color of the i-th ball from the left is Color C_i, and an integer X_i is written on it.
Takahashi wants to rearrange the balls so that the integers written on the balls are non-decreasing from left to right. In other words, his objective is to reach a situation where, for every 1\leq i\leq N-1, the number written on the (i+1)-th ball from the left is greater than or equal to the number written on the i-th ball from the left.
For this, Takahashi can repeat the following operation any number of times (possibly zero):
Choose an integer i such that 1\leq i\leq N-1.
If the colors of the i-th and (i+1)-th balls from the left are different, pay a cost of 1. (No cost is incurred if the colors are the same).
Swap the i-th and (i+1)-th balls from the left.
Find the minimum total cost Takahashi needs to pay to achieve his objective.
Constraints
- 2 \leq N \leq 3\times 10^5
- 1\leq C_i\leq N
- 1\leq X_i\leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N C_1 C_2 \ldots C_N X_1 X_2 \ldots X_N
Output
Print the minimum total cost Takahashi needs to pay to achieve his objective, as an integer.
Sample Input 1
5 1 5 2 2 1 3 2 1 2 1
Sample Output 1
6
Let us represent a ball as (Color, Integer). The initial situation is (1,3), (5,2), (2,1), (2,2), (1,1). Here is a possible sequence of operations for Takahashi:
- Swap the 1-st ball (Color 1) and 2-nd ball (Color 5). Now the balls are arranged in the order (5,2), (1,3), (2,1), (2,2), (1,1).
- Swap the 2-nd ball (Color 1) and 3-rd ball (Color 2). Now the balls are arranged in the order (5,2), (2,1), (1,3), (2,2), (1,1).
- Swap the 3-rd ball (Color 1) and 4-th ball (Color 2). Now the balls are in the order (5,2), (2,1), (2,2), (1,3), (1,1).
- Swap the 4-th ball (Color 1) and 5-th ball (Color 1). Now the balls are in the order (5,2), (2,1), (2,2), (1,1), (1,3).
- Swap the 3-rd ball (Color 2) and 4-th ball (Color 1). Now the balls are in the order(5,2), (2,1), (1,1), (2,2), (1,3).
- Swap the 1-st ball (Color 5) and 2-nd ball (Color 2). Now the balls are in the order (2,1), (5,2), (1,1), (2,2), (1,3).
- Swap the 2-nd ball (Color 5) and 3-rd ball (Color 1). Now the balls are in the order (2,1), (1,1), (5,2), (2,2), (1,3).
After the last operation, the numbers written on the balls are 1,1,2,2,3 from left to right, which achieves Takahashi's objective.
The 1-st, 2-nd, 3-rd, 5-th, 6-th, and 7-th operations incur a cost of 1 each, for a total of 6, which is the minimum. Note that the 4-th operation does not incur a cost since the balls are both in Color 1.
Sample Input 2
3 1 1 1 3 2 1
Sample Output 2
0
All balls are in the same color, so no cost is incurred in swapping balls.
Sample Input 3
3 3 1 2 1 1 2
Sample Output 3
0
Takahashi's objective is already achieved without any operation.