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..

Square Root Decomposition 우리 말로는 평방 분할(Sqrt Decomposition)이라고 불리는 이 기술은 특정 구간에 대한 질문(query)에 빠르게 답하기 위한 최적화 기술(일종의 자료구조)이다. 먼저, 아래와 같은 문제에 대해 고민해보자. 원소의 개수가 \(n\) 개인 배열 arr[]이 있다. 이 배열에 대해서 \(q\) 개의 질문(query)이 하나씩 들어온다. 질문의 내용은 다음 2가지 중 하나이다.특정 구간 [\(l, \ r\)] 의 합을 구하라.특정 위치 \(idx\) 의 값을 \(val\) 로 변경하라. 위와 같은 문제는 단순하게 반복문을 이용하여 \(l\) 부터 \(r\) 까지 순회하면서 값을 더해나가면 구할 수 있다(시간복잡도: \(O(q \times n)\)). ..