Сканирующая прямая & корневая оптимизация

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