Олимпиадный тренинг

Задача . F. Точки


Задача

Темы: Комбинаторика математика матрицы реализация Структуры данных *2500

Тройка точек \(i\), \(j\) и \(k\) на координатной прямой считается красивой, если \(i < j < k\) и \(k - i \le d\).

Вам задано множество точек на координатной прямой, изначально пустое. Вам нужно обрабатывать запросы трех типов:

  • добавить точку в множество;
  • удалить точку из множества;
  • посчитать количество красивых троек из точек, принадлежащих множеству.
Входные данные

В первой строке заданы два целых числа \(q\) и \(d\) (\(1 \le q, d \le 2 \cdot 10^5\)) — количество запросов и параметр, по которому определяется, является ли тройка красивой.

Во второй строке заданы \(q\) целых чисел \(a_1, a_2, \dots, a_q\) (\(1 \le a_i \le 2 \cdot 10^5\)). Число \(a_i\) обозначает \(i\)-й запрос следующим образом:

  • если точка \(a_i\) входит в множество, удалить ее; иначе добавить ее;
  • после удаления или добавления точки надо вывести количество красивых троек.
Выходные данные

Для каждого запроса выведите одно целое число — количество красивых троек после обработки запроса.


Примеры
№Входные данныеВыходные данные
1 7 5
8 5 3 2 1 5 6 
0
0
1
2
5
1
5

time 6500 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет