해결한 사람
0
명
정답률
0.00
%
시간 제한
4000
ms
메모리 제한
489
MB
Anton은 순열을 좋아하며, 특히 순열의 원소들을 재배열하는 것을 좋아한다. n개 원소의 순열은 수열 {a1, a2, ..., an}이며, 1부터 n까지의 모든 수가 정확히 한 번씩 등장한다는 점에 유의하라.
어느 날 Anton은 새로운 순열을 얻어 이를 가지고 놀기 시작했다. 그는 다음 연산을 q번 수행한다. 순열에서 두 원소를 골라 서로 바꾼다. 각 연산 후에는 친구 Vanya에게 새 순열에 역전이 몇 개 있는지 묻는다. 순열의 역전 수는 1 ≤ i < j ≤ n이고 ai > aj인 서로 다른 순서쌍 (i, j)의 개수이다.
Vanya는 Anton의 어리석은 질문에 답하는 데 지쳤다. 그래서 자신을 대신해 이 질문들에 답할 프로그램을 작성해 달라고 당신에게 부탁했다.
Initially Anton's 순열은 {1, 2, ..., n}였다. 즉, 1 ≤ i ≤ n인 모든 i에 대해 ai = i이다.
입력의 첫 번째 줄에는 두 정수 n와 q (1 ≤ n ≤ 200 000, 1 ≤ q ≤ 50 000)가 주어지며, 각각 순열의 길이와 Anton이 수행하는 연산의 수이다.
이어지는 입력의 q개 줄에는 각각 두 정수 li와 ri (1 ≤ li, ri ≤ n)가 주어지며, Anton이 i-th 연산에서 서로 바꾸는 원소들의 인덱스이다. Anton이 i-th 연산에서 서로 바꾸는 원소들의 인덱스는 같을 수도 있음에 유의하라. 순열의 원소에는 하나부터 번호가 매겨져 있다.
q개의 줄을 출력한다. 출력의 i-th 줄에는 i-th 연산 후 Anton의 순열에 있는 역전의 수를 출력한다.
2 1
2 1
1
5 4
4 5
2 4
2 5
2 2
1
4
3
3
6 7
1 4
3 5
2 3
3 3
3 6
2 1
5 1
5
6
7
7
10
11
8
첫 번째 예제를 살펴보자.
Anton의 첫 번째 연산 후 순열은 {1, 2, 3, 5, 4}가 된다. 여기에는 역전이 하나뿐이며, (4, 5)이다.
Anton의 두 번째 연산 후 순열은 {1, 5, 3, 2, 4}가 된다. 역전은 네 개이며, (2, 3), (2, 4), (2, 5), (3, 4)이다.
Anton의 세 번째 연산 후 순열은 {1, 4, 3, 2, 5}가 된다. 역전은 세 개이며, (2, 3), (2, 4), (3, 4)이다.
Anton의 네 번째 연산 후에는 순열이 바뀌지 않으므로, 여전히 역전이 세 개이다.