Совпали по шагам

В школьном чате ребята сравнивают, сколько шагов за день показал их браслет. Два человека считают свои результаты «похожими», если разница между числом шагов не больше, чем d.

Посчитайте, сколько существует неупорядоченных пар учеников (то есть пар (i, j) с i < j), у которых результаты похожи.

Важно: ответ может не поместиться в 32-битный тип, используйте 64-битные целые (в Python это не проблема).

Формат ввода

В первой строке записано целое число t — количество наборов данных. Далее идут t наборов данных. В каждом наборе в первой строке записаны два целых числа n и d. Во второй строке записаны n целых чисел — результаты учеников.

Формат вывода

Для каждого набора данных выведите одно целое число — количество пар (i, j), где i < j и |a[i] − a[j]| ≤ d. Ответы выводите с новой строки.

Ограничения

• 1 ≤ t ≤ 4
• 1 ≤ n ≤ 12000
• 0 ≤ d ≤ 1 000 000
• 0 ≤ a[i] ≤ 1 000 000
• Сумма значений n по всем наборам данных не превышает 12000.

Пример

Ввод:

3
1 0
0
2 5
0 5
2 5
0 6

Вывод:

0
1
0

Ключевое наблюдение: если отсортировать массив a, то для любых l < r условие |a[l] - a[r]| <= d превращается в просто a[r] - a[l] <= d (модуль не нужен, потому что a[r] >= a[l]). Тогда все подходящие пары для фиксированного l образуют непрерывный отрезок по r.

Приём: два указателя. Двигаем правый указатель только вперёд, поэтому суммарно он сделает не больше n шагов — получается линейный проход после сортировки.

План:

• Считай n, d и массив, отсортируй его.
• Заведи ans = 0 и указатель r = 0.
• Для каждого l от 0 до n-1:
• Убедись, что r >= l+1 (иначе поставь r = l+1).
• Пока r < n и a[r] - a[l] <= d, увеличивай r.
• Теперь r — первый индекс, где условие ломается, значит подходящих j ровно r - l - 1.

Добавь к ответу: ans += (r - l - 1).

Мини-сниппет формулы подсчёта: ans += r - l - 1

Сложность: сортировка O(n log n), проход двумя указателями O(n), память O(1) сверх массива.

Частая ошибка: сбрасывать r назад для каждого l (тогда выйдет O(n^2)), или посчитать пары дважды. Здесь каждая пара учитывается ровно один раз, потому что фиксируем левый индекс и берём только j > l.