$ Сканирующая прямая & корневая оптимизация
vb = [Ваня]
sk = [Сережа.K]
sm = [Сережа.М]
# $sk$ С/C++ : bitset<100>
# $vb$ Дерево отрезков с групповыми операциями
## Присваивание на отрезке и минимум на отрезке
## Прибавление на отрезке и сумма на отрезке
# $vb$ Сканирующая прямая (она же заметающая, она же scanline, sweepline)
## Задача "количество точек в прямоугольнике"
## Задача "возрастающая последовательность точек"
## Задача "количество k-инверсий в массиве за O(nklogn)"
## Задача "для каждой точки узнать, сколько раз она покрыта прямоугольниками"
## Задача "площадь объединения прямоугольников"
# $sk$ Дерево отрезков: количество черных отрезков
# $sk$ C/C++
## merge, lower\_bound, upper\_bound, sort
## свой компаратор для всех этих функций
# $sk$ Корневая оптимизация
## Отложенные операции
### Частичные суммы → сумма на меняющемся массиве
### Сколько чисел x : l ≤ x ≤ r? Бинарный поиск. А теперь числа можно добавлять.
### Сколько точек в прямоугольнике (см. сканирующую прямую)? А теперь точки добавляются.
## Разбиение массива на куски
### Считаем сумму и минимум на отрезке за корень.
### Изменяем массив на отрезке.
### Двухмерный запрос: l ≤ i ≤ r, x ≤ a_i ≤ y
### split & rebuild
### reverse на отрезке + те же запросы, что и раньше
# $sk$ Простейшее 2D-дерево (дерево отрезков сортированных массивов)
## Построение за O(nlogn) через merge
## Запрос за O(log^2n) деревом отрезков снизу и lower\_bound