Изменения

===Нахождение всех интерваловотрезков, покрывающих данную точку===

# Для заданной точки <tex>x</tex> вычислить количество интерваловотрезков, которые её покрывают.

Для решения данной задачи воспользуемся списком с пропусками. Когда нам приходит запрос первого типа, то мы просто добавляем числа <tex>L</tex> и <tex>R</tex> в список с пропусками (если какое-то из чисел уже было добавлено, то второй раз мы его не добавляем). После этого идём с верхнего уровня, и на каждом уровне мы ищем такие <tex>l</tex> и <tex>r</tex>, что значение <tex>l</tex> не больше <tex>L</tex>, а значение следующего за <tex>l</tex> элемента уже больше <tex>L</tex>. Аналогично ищем такое же <tex>r</tex>, только относительно <tex>R</tex>. Если значения <tex>l.next</tex> и <tex>r</tex> лежат полностью внутри отрезка <tex>[L, R]</tex>, то к самому отрезку <tex>[l.next, r]</tex> прибавляем <tex>1</tex>, а сам отрезок <tex>[L, R]</tex> разбиваем на два три <tex>[L, l.next.key - 1]</tex>, <tex>[l.next.key, r.key]</tex> и <tex>[r.key + 1, R]</tex> и по отдельности прибавляем решаем задачу уже отрезки для отрезков <tex>[L, l.next.key - 1]</tex> и <tex>[r.key + 1, R]</tex> (если для какого-то отрезка левая граница стала больше правой, то мы ничего не делаем). Допустим, что на каком-то уровне у нас получилось разделить отрезок <tex>[L, R]</tex> на <tex>3</tex> части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза только с одной стороны, поскольку другая часть отрезка уже будет иметь точную границуполностью лежать в <tex>[l.next.key, r.key]</tex>. Итого время обработки запроса <tex>O(\log{n})</tex>.

Для запросов второго типа мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне найдём тот элемент, значение которого не меньше точки <tex>x</tex>. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. ОчевидноПоскольку уровней всего <tex>\log{n}</tex>, что а на каждом уровне обойдём не более двух элементов, то данный тип запросов мы обрабатываем обработаем за <tex>O(\log{n})</tex>.