robustflame의 블로그

문제링크 - http://codeforces.com/problemset/problem/785/E문제 풀이순열 \(a[ \ ] = \{1, 2, ..., n\} \ (1 \le n \le 200000)\) 에 대하여 특정 위치 \(l_i\) 과 \(r_i\) 의 값을 바꾸는 연산이 \(q \ (1 \le q \le 50000)\) 번 수행될 때, 매 연산 후 순열에 존재하는 역접(inversion)의 수를 세는 문제다. 역접의 수는 크기가 \(a[x] > a[y] \ (x a[r]\) 이면 역접의 수가 1 감소한다. 위의 내용들에서 서로 상쇄되는 것들을 제거하고, 통합하면 아래와 같이 간결하게 역접의 수 변화를 확인할 수 있다. \(a[l] < a[r]\) 이면, \((l 0) { ret += tree[p..