Swap Swap Sort
시간 제한3초메모리 제한512 MB
1부터 K까지의 목표 순열에 인접 교환을 가하며, 각 교환 뒤 고정된 배열을 그 순서로 정렬하는 데 필요한 최소 인접 교환 횟수를 구한다.
문제
1 이상 K 이하의 정수 N개로 이루어진 배열이 있다. 친구에게는 1부터 K까지의 수를 임의의 순서로 정렬할 수 있는 알고리즘이 있다. 이 알고리즘은 배열에서 인접한 두 원소를 맞바꾸는 swap 연산을 여러 번 수행한다. 알고리즘은 배열을 정렬하는 데 필요한 최소 횟수의 swap만 수행한다.
1부터 K까지의 수의 정렬 순서는 목표 순열로 주어진다. 목표 순열은 1부터 K까지의 각 수가 정확히 한 번씩 나타나는 수열이며, 그 순서가 원하는 정렬 순서이다.
예를 들어 배열 [1 4 2 1 2]를 목표 순열 4, 1, 2, 3으로 정렬하면 [4 1 1 2 2]가 된다.
여러 목표 순열에 대해 친구의 알고리즘이 수행하는 swap 횟수가 궁금해졌다. 이를 알아보기 위해 목표 순열 1, 2, ..., K에서 시작해 Q번의 연산을 수행한다. 각 연산은 목표 순열에서 인접한 두 원소를 맞바꾼다. 각 연산을 수행한 뒤, 현재 목표 순열로 친구의 알고리즘을 실행했을 때 수행할 swap 횟수를 구한다. Q번의 연산은 목표 순열을 누적해서 바꾸지만 배열에는 영향을 주지 않는다.
입력
첫째 줄에 세 정수 N, K, Q가 주어진다. (1 ≤ K ≤ N ≤ 100 000, 1 ≤ Q ≤ 1 000 000)
둘째 줄에 배열을 나타내는 N개의 정수 a1, a2, ..., aN이 주어진다. (1 ≤ ai ≤ K)
다음 Q개 줄에 각각 정수 j가 하나씩 주어진다. (1 ≤ j ≤ K-1) 이는 목표 순열의 j번째와 j+1번째 원소를 맞바꾸는 연산이다.
출력
Q번의 연산 각각에 대해, 현재 목표 순열에 대한 답을 한 줄에 하나씩 출력한다.
힌트
세 목표 순열은 차례로 1, 2, 4, 3, 그다음 1, 4, 2, 3, 그다음 4, 1, 2, 3이다. 마지막 목표 순열에 대해 친구의 알고리즘은 배열 [1 4 2 1 2]를 [4 1 1 2 2]로 정렬하는 데 swap을 두 번 사용한다.