686. Следующий
Реализуйте структуру данных,
которая поддерживает множество S целых чисел, с которым разрешается производить
следующие операции:
·
add(i) – добавить в множество S
число i (если оно там уже есть, то
множество не меняется);
·
next(i) – вывести минимальный
элемент множества, не меньший i. Если
искомый элемент в структуре отсутствует, необходимо вывести –1.
Вход. Исходное
множество S пусто. Первая строка входного файла содержит n – количество операций (1 ≤ n ≤ 300 000). Следующие n
строк содержат операции. Каждая операция имеет вид либо "+ i", либо "? i". Операция "? i" задает запрос next(i).
Если
операция "+ i" идет во
входном файле в начале или после другой операции "+", то она задает
операцию add(i). Если же она идет
после запроса "?" и результат этого запроса был y, то выполняется операция add((i
+ y) mod 109).
Во
всех запросах и операциях добавления параметры лежат в интервале от 0 до 109.
Выход. Для каждого запроса выведите
одно число – ответ на запрос.
6
+ 1
+ 3
+ 3
? 2
+ 1
? 4
Пример выхода
3
4
структуры данных – декартово дерево,
явный ключ
Для
решения задачи используем декартово дерево с явным ключом. Достаточно
реализовать операции вставки элемента в дерево и нахождения минимального элемента множества,
не меньшего i. Для реализации
последней операции достаточно разрезать дерево по ключу i (получив левое L и
правое R дерево), после чего вернуть
минимальный ключ дерева R.
Пример
Рассмотрим приведенный в примере
тест.
Вход |
Операция |
Содержимое множества S |
Выводимое значение |
+ 1 |
add(1) |
{1} |
|
+ 3 |
add(3) |
{1, 3} |
|
+ 3 |
add(3) |
{1, 3} |
|
? 2 |
next(2) |
{1, 3} |
3 |
+ 1 |
add(1 + 3) = add(4) |
{1, 3, 4} |
|
? 4 |
next(4) |
{1, 3, 4} |
4 |
Реализация алгоритма
Объявим структуру item вершины декартового дерева. Объявим
указатель pitem на нее.
struct item
{
int Key,
Priority;
item *l, *r;
item() { }
item (int
Key, int Priority) :
Key(Key), Priority(Priority), l(NULL),
r(NULL) { }
};
typedef item* pitem;
Функцию split разрезания дерева t по ключу Key реализуем так, чтобы элемент дерева, равный ключу Key, отходил в правое поддерево r.
void split (pitem t, int Key, pitem &l, pitem &r)
{
if (!t)
l = r = NULL;
else if (Key <= t->Key)
split (t->l, Key, l, t->l), r = t;
else
split (t->r, Key, t->r, r), l = t;
}
Функция merge сливает два
декартовых дерева l и r в t.
void merge (pitem l, pitem r, pitem
&t)
{
if (!l || !r)
t = l ? l : r;
else if (l->Priority > r->Priority)
merge (l->r, r, l->r), t = l;
else
merge (l, r->l, r->l), t = r;
}
Функция GetMin
возвращает минимальный ключ в дереве t.
int GetMin(pitem t)
{
if (t ==
NULL) return -1;
if (t->l
== NULL) return t->Key;
return
GetMin(t->l);
}
Реализация
операции add. Если элемент с ключом i
уже присутствует в дереве, то после разреза он будет минимальным в R. В таком случае (когда GetMin(R) равно i) ничего добавлять не надо, но следует склеить дерево Tree обратно. Иначе добавляем новый
элемент с ключом i методом вклейки.
Приоритет каждого нового элемента выбираем произвольно при помощи функции
rand(), чтобы строящееся декартово дерево Tree
было максимально сбалансировано.
void add(int
i)
{
split(Tree,i,L,R);
if(GetMin(R)
!= i)
{
merge(L,new
item(i,rand()),Tree);
merge(Tree,R,Tree);
}
else
merge(L,R,Tree);
}
Реализация
операции next. Разрезаем дерево Tree
по ключу i. Выводим минимальный
элемент правого полученного дерева R.
Собираем дерево Tree обратно.
void next(int
i)
{
split(Tree,i,L,R);
y = GetMin(R);
printf("%d\n",y);
merge(L,R,Tree);
}
Основная часть программы. Читаем
входные данные и обрабатываем запросы. Переменную y устанавливаем в MINF = -2000000000, если
предыдущим не был запрос “?”.
#define MINF -2000000000
int y = MINF;
scanf("%d\n",&n);
while(n--)
{
scanf("%c %d\n",&c,&i);
if (c == '+')
{
if (y >
MINF) i = (i + y) % 1000000000, y = MINF;
add(i);
}
else next(i);
}