배수 역전
플래티넘 V의견: 0
길이 \(N\)의 양의 정수 수열 \(a_1, \dots, a_N\) 과 정수 \(c\) 가 주어진다. 다음을 만족하는 순서쌍 \((i, j)\) 의 개수를 구하여라.
- \(i < j\)
- \(a_i > c \cdot a_j\)
\(c=1\) 이면 일반적인 역전이지만, 임의의 \(c\) 에 대해 일반화된 문제이다. \(N\)이 크므로 분할 정복으로 \(O(N \log N)\) 에 풀어야 한다.
\(1 \le N \le 200{,}000\)
\(1 \le c \le 10^9\)
\(1 \le a_i \le 10^9\)
첫째 줄에 \(N\)과 \(c\)가 주어진다.
둘째 줄에 \(N\)개의 양의 정수 \(a_1, \dots, a_N\)이 주어진다.
조건을 만족하는 순서쌍의 개수를 출력한다.
5 2
9 4 3 1 8
5\(c=2\). \(a_i>2a_j\) 인 쌍: \((9,4)\) 는 \(9>8\), \((9,3)\) 는 \(9>6\), \((9,1)\) 은 \(9>2\), \((4,1)\) 은 \(4>2\), \((3,1)\) 은 \(3>2\). 총 5개이다.
3 1
1 2 3
0\(c=1\), 수열이 순증가하므로 \(a_i>a_j\) 인 쌍이 없어 답은 0이다.
riseoj 작성
출처 Original
평가 및 의견
배수 역전
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
배수 역전