$ Деревья отрезков (3 декабря)

d = @link:[code]:../src/2015-12-03

# <font color=red>[10 минут]</font> feelgood: даны a_i > 0, найти отрезок такой, что min &times; &sum; &rarr; max 
## Напоминание: у нас уже было решение за O(n) стеком...
## Решение с помощью СНМ
## Решение деревом отрезков

# <font color=red>[20 минут]</font> Задачи на дерево отрезков (кодим)
## Снизу: присваивание в точке, сумма на отрезке $d$/down.cpp.html
## Сверху: присваивание в точке, сумма на отрезке $d$/up.cpp.html
## Динамическое $d$/up_dynamic.cpp.html
## Фенвика $d$/fenwick.cpp.html

# <font color=red>[30 минут]</font> Задачи на дерево отрезков
## Другие операции на отрезке: произведение чисел на отрезке, произведение матриц, сумма линейных функций, gcd на отрезке
## painter: число черных отрезков, суммарная длина черного, операция "покрасить отрезок"
## nearandmore: get(i, x): ближайший j &ge; i: a[j] &ge; x; set(i, x): a[i] = x;

# <font color=red>[30 минут]</font> Задачи на заметающую (сканирующую) прямую
## Offline. Даны m прямоугольников и n точек. Для каждого прямоугольника найти количество точек в нем. O((n+m)logn)
## Offline. Для перестановки на отрезке [l,r] научиться находить кол-во чисел от x до y
## Offline. Количество пар вложенных отрезков на прямой
## Количество k-инверсий в массиве за O(nklogn)