Изменения

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