Изменения

Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть <tex>-</tex> — на третьем и так далее, но при этом известно, что если элемент расположен на уровне <tex>i</tex>, то он также расположен на всех уровнях с номерами меньших , номера которых меньше <tex>i</tex>.

На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне <tex>-</tex> — всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.

Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которое которого есть начало <tex>\mathtt{head}</tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.

Элементы односвязного списка <tex>-</tex> — вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:* <tex>\mathtt{next}</tex> <tex>-</tex> — ссылка на следующий элемент списка* <tex>\mathtt{key}</tex> <tex>-</tex> — ключ, который хранится в данной вершине* <tex>\mathtt{down}</tex> <tex>-</tex> — ссылка на соответственный элемент, лежащий уровнем ниже

'''list''' build_lvl ('''list''' lvl) <font color=darkgreen>// Отсеивание нечётных элементов</font>

'''node''' cur = next_lvl.head '''while''' (i != <tex>\neq</tex> ''null'') '''and''' (i != lvl.tail)next <tex>\neq</tex> ''null'' next_lvlcur.push_back(next = node(i.key, i, cur.next)) <font color=darkgreen>// Конструктор node(key, down, next) возвращает новую вершину с ключом key , ссылками down на нижний и ссылкой down next на соответствующую вершину предыдущего уровеняследующий элемент</font> cur = cur.next i = i.next.next <font color=darkgreen>// Переход к следующему чётному элементу</font>

'''list''' skip_list ('''list''' l): '''list''' lvl = build_lvl(l) <font color=darkgreen>// Построение первого уровня</font> '''while''' lvl.size > 2 <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font>

'''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>

# Переместиться на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне <tex>-</tex> — прекратить поиск и вернуть ссылку на текущую вершину

'''T''' find ('''node''' res, '''K''' key) '''while''' res.key < key <font color=darkgreen>// Пока значение вершины меньше ключа</font> res = res.next <font color=darkgreen>// Перейдём к следующей вершине в текущем уровне</font> '''if''' res.down = ''null'' <font color=darkgreen>// Если мы находимся на первом уровне</font> '''return''' res <font color=darkgreen>// Мы нашли искомый элемент</font> '''return''' find(res.down, key) <font color=darkgreen>// Иначе спустимся на один уровень ниже</font>

# Пока следующих элемент значение следующего элемента меньше ключа <tex>-</tex> идём по списку вправо— переходим к следующему элементу.# Если мы на первом уровне <tex>-</tex> — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>.# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе <tex>-</tex> — ''null''. Если мы были не на первом уровне и нам вернули ''null'' <tex>-</tex> — возвращаем его без броска монетки.

Функция <tex>\mathtt{insert}</tex> возвращаем ссылку на вставленный элемент в списке, в котором находится <tex>\mathtt{res}</tex>, или ''null'', если на монете выпал не «Орёл»выпала «Решка».

'''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.next <tex>\neqkey </tex> ''null''key res = res.next '''node''' down_node

res.next down_node = node(key, ''null'', res.next) '''ifelse''' random(0, 1) > 0.5 '''return''' res.next '''return''' ''null'' node i down_node = insert(res.down, key) '''if''' i down_node <tex>\neq</tex> ''null'' res.next = node(key, idown_node, res.next) '''if''' random(0, 1) > 0.5 <font color=darkgreen>// Бросок монеты</font>

# Переходим к следующему элементу, пока значение следующего элемента меньше ключа# Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне и нашли элемент <tex>-</tex> , то просто удаляем элемент# Иначе спускаемся ниже и также удаляем элемент ещё с текущего нижнего уровня, если он есть.

* <tex>\{0, 1\}</tex> {{---}} — <tex>O(n)</tex> <tex>-</tex> — поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.* <tex>\{1, 0\}</tex> {{---}} — зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>O(n)</tex>.

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