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

문제링크 - http://codeforces.com/contest/777/problem/E문제 분류난이도 - 중태그 - dynamic programming, data structure, segment tree문제 풀이내부 반지름의 길이 \(a_i\), 외부 반지름의 길이 \(b_i\), 그리고 높이 \(h_i\)가 주어진 여러 개의 링들을 최대한 높게 쌓는 문제다. 일단 아래와 같이 2차원 평면으로 보면 (1) \(b_i\)가 증가하는 순으로, (2) \(b_i\)가 증가하는 순으로 정렬해야할 필요성을 느낄 수 있다. 완전 탐색을 할 경우 \(O(2^n)\)으로 문제를 해결할 수 있다. 너무 느리므로 동적계획법을 고민해보면 아래와 같은 점화식을 찾을 수 있다. \(dp[i]\): \(i\)번 링을 맨 밑..