실시간 순위 시스템에서 각 참가자의 점수가 길이 \(N\) 인 배열 \(a_1, a_2, \dots, a_N\) 으로 저장되어 있다. 이 배열의 역전수(inversion count)란, \(i < j\) 이면서 \(a_i > a_j\) 인 순서쌍 \((i, j)\) 의 개수이다. 즉 앞에 있는 점수가 뒤에 있는 점수보다 큰 쌍의 개수로, 순위가 얼마나 뒤섞여 있는지를 나타내는 척도이다.

이제 \(Q\) 번의 점수 갱신이 차례로 들어온다. 각 갱신은 "위치 \(p\) 의 점수를 \(v\) 로 바꾼다"로 이루어지며, 매 갱신을 적용한 직후의 역전수를 출력해야 한다.

예를 들어 배열이 \([3, 1, 4, 1, 5]\) 라면 역전수는 \(3\) 이다 (\((3,1), (3,1), (4,1)\)). 여기서 세 번째 값을 \(0\) 으로 바꾸어 \([3, 1, 0, 1, 5]\) 가 되면 역전수는 \(4\) 가 된다.

갱신마다 배열 전체를 다시 세면 너무 느리다. 한 위치의 값만 바뀌었을 때 그 위치가 관여하는 쌍들만 살펴보면 역전수의 변화량을 빠르게 계산할 수 있다는 점을 이용하라.

\(1 \le N \le 200{,}000\)

\(1 \le Q \le 200{,}000\)

\(1 \le p \le N\)

모든 점수의 절댓값은 \(10^9\) 이하이다.

역전수는 최대 \(\binom{N}{2} \approx 2 \times 10^{10}\) 까지 커질 수 있으므로 64비트 정수를 사용해야 한다.

첫째 줄에 두 정수 \(N\) 과 \(Q\) (\(1 \le N \le 200{,}000\), \(1 \le Q \le 200{,}000\)) 가 주어진다.

둘째 줄에 \(N\) 개의 정수 \(a_1, a_2, \dots, a_N\) 이 주어진다.

이어서 \(Q\) 개의 줄에 각각 두 정수 \(p\) 와 \(v\) (\(1 \le p \le N\)) 가 주어지며, 위치 \(p\) (1-based) 의 점수를 \(v\) 로 바꾸라는 뜻이다.

입력되는 모든 점수의 절댓값은 \(10^9\) 이하의 정수이다.

총 \(Q\) 개의 줄을 출력한다. \(k\) 번째 줄에는 \(k\) 번째 갱신을 적용한 직후의 배열의 역전수를 출력한다.

riseoj 작성

출처 Original