창구 대기 행렬의 우대 쌍

문제

한 은행 창구에 N명의 고객이 도착한 순서대로 줄을 서 있다. i번째로 도착한 고객에게는 우선도 점수 a_i가 매겨져 있다. 창구 직원은 줄에서 서로 다른 두 고객 i, j (i < j, 즉 i가 먼저 도착했다)를 짝지어 보고, 두 점수의 차이가 기준값 K를 넘는지에 따라 쌍을 세 종류로 나눈다. 먼저 온 고객의 점수가 늦게 온 고객의 점수보다 K를 초과하여 크면, 곧 a_i - a_j > K이면 이 쌍은 앞선 우대 쌍이다. 늦게 온 고객의 점수가 먼저 온 고객의 점수보다 K를 초과하여 크면, 곧 a_j - a_i > K이면 이 쌍은 뒤선 우대 쌍이다. 두 경우 모두 아니면 비슷한 쌍이다. 차이가 정확히 K인 쌍은 우대 쌍이 아니라 비슷한 쌍이며, 점수가 같은 고객끼리의 쌍도 비슷한 쌍이다. 한 쌍은 위 세 종류 중 정확히 하나에 속한다. 줄 전체에서 가능한 모든 쌍 N(N-1)/2개에 대해 앞선 우대 쌍, 뒤선 우대 쌍, 비슷한 쌍의 개수를 각각 구하시오. 줄을 반으로 나누어 각각 처리한 뒤 두 반쪽에 걸친 쌍을 세는 재귀적 방법을 쓰면 효율적으로 풀 수 있다.

입력

첫 줄에 정수 N, K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 0 ≤ K ≤ 10^9) 둘째 줄에 a_1, a_2, ..., a_N이 공백으로 구분되어 주어진다. (0 ≤ a_i ≤ 10^9)

출력

한 줄에 앞선 우대 쌍의 수, 뒤선 우대 쌍의 수, 비슷한 쌍의 수를 공백으로 구분하여 출력한다.

5 2
5 1 4 9 2

3 4 3

1 0
7

0 0 0

4 0
3 3 1 3

2 1 3

출처: Devin.KR 자체 제작