Деревья отрезков (2 декабря 2016)

1. [10 минут] feelgood: даны a_i > 0, найти отрезок такой, что min × ∑ → max
1. Напоминание: у нас уже было решение за O(n) стеком...
2. Решение с помощью СНМ
3. Решение деревом отрезков
2. [20 минут] Задачи на дерево отрезков (кодим)
1. Снизу: присваивание в точке, сумма на отрезке [code]
2. Сверху: присваивание в точке, сумма на отрезке [code]
3. Динамическое [code]
3. [30 минут] Задачи на дерево отрезков
1. Другие операции на отрезке: произведение чисел на отрезке, произведение матриц, сумма линейных функций, gcd на отрезке
2. painter: число черных отрезков, суммарная длина черного, операция "покрасить отрезок"
3. nearandmore: get(i, x): ближайший j ≥ i: a[j] ≥ x; set(i, x): a[i] = x;
4. [30 минут] Задачи на заметающую (сканирующую) прямую
1. Offline. Даны m прямоугольников и n точек. Для каждого прямоугольника найти количество точек в нем. O((n+m)logn)
2. Offline. Для перестановки на отрезке [l,r] научиться находить кол-во чисел от x до y
3. Offline. Количество пар вложенных отрезков на прямой
4. Количество k-инверсий в массиве за O(nklogn)