문제
1부터 N으로 구성된 N개의 숫자 배열이 주어진다. 이 배열에 대해 다음과 같은 동작을 할 수 있다.
A) 숫자 Y앞에 숫자 X를 배치한다. B) 숫자 Y뒤에 숫자 X를 배치한다.
이러한 동작들을 통해 숫자를 새로이 배치했을 때, 원래 상태로 되돌아가게 하고자 한다. 되돌리기 위해서도 역시 위의 동작을 수행해야 하며, 가능한 방법 중 최소 횟수를 찾아야 한다.
입력
입력의 첫 번째 줄에는 N(2≤N≤500,000)과 M(0≤M≤100,000)이 입력된다.
M개의 줄에선 배열에서 취할 수 있는 동작이 입력되며, c X Y 형식으로 입력된다.
여기서 c는 동작 A인지 B인지를 뜻하는 대문자 'A'나 'B'가 입력되며, X나 Y에는 1부터 N의 숫자가 입력된다. X와 Y가 같은 경우는 존재하지 않는다.
출력
입력된 명령을 수행한 다음 원래 배치대로 되돌리기 위한 최소 횟수를 출력한다.
예제 #1
4 3
B 1 2
A 4 3
B 1 4
2
예제 #2
6 5
A 1 4
B 2 5
B 4 2
B 6 3
A 3 5
3
출처
COCI 2006/2007 contest3 6 (변형)
로그인해야 코드를 작성할 수 있어요.