Компания Giggle
открывает свой новый офис в Судиславле, и Вы приглашены на собеседование. Ваша
задача – решить поставленную задачу.
Вам нужно
создать структуру данных, которая представляет собой массив целых чисел. Изначально
массив пуст. Вам нужно поддерживать две операции:
·
запрос: "? i j" - возвращает
минимальный элемент между i-ым и j-м включительно;
·
изменение: "+ i x" – добавить
элемент x после i-го элемента списка. Если i
= 0, то элемент добавляется в начало массива.
Конечно, эта
структура должна быть достаточно хорошей.
Вход. Первая строка содержит количество операций n (1 ≤ n ≤ 200000) над массивом. Следующие n строк описывают сами операции. Все операции добавления являются
корректными. Все числа, хранящиеся в массиве, по модулю не превосходят 109.
Выход. Для каждой
операции ? в отдельной строке выведите её результат.
|
Пример входа |
Пример выхода |
|
8 + 0 5 + 1 3 + 1 4 ? 1 2 + 0 2 ? 2 4 + 4 1 ? 3 5 |
4 3 1 |
РЕШЕНИЕ
структуры данных – декартово дерево,
неявный ключ
Элементы будем
добавлять в декартово дерево с неявным ключом, которое поддерживает операцию
минимума.
Вычисление
минимума на отрезке [i; j]: вырезаем поддерево от i-ой до j-ой вершины, после чего возвращаем минимум на нем.
Добавление элемента
x после i-го элемента: разбиваем дерево на два (в l заносим первые i
вершин, в r – остальные), после чего
объединяем l с деревом из одного
элемента x, а результат объединяем с r.
Объявим MAX
равным максимальному значению.
#define MAX 2000000000
Структура вершины Item имеет следующий вид. Приоритет
будем устанавливать рандомизировано.
struct Item
{
int cnt, x, Min, Priority;
Item *l, *r;
Item() { }
Item (int x) : Priority((rand() <<
16u) + unsigned(rand())),
x(x), Min(x), l(NULL),
r(NULL) { }
};
int min(int x , int y)
{
return (x < y) ? x : y;
}
int cnt(Pitem t)
{
return t ? t->cnt : 0;
}
long long GetMin(Pitem t)
{
return t ? t->Min : MAX;
}
void upd(Pitem t)
{
if (t)
{
t->cnt = 1 + cnt(t->l) + cnt (t->r);
t->Min = min(t->x, min(GetMin(t->l),GetMin(t->r)));
}
}
Слияние деревьев 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;
upd(t);
}
В дерево l заносится pos вершин
дерева t, в дерево r все остальные.
void Split(Pitem t, Pitem &l, Pitem &r, int pos)
{
if (!t) return void( l = r = 0 );
if (pos <= cnt(t->l))
Split(t->l, l, t->l, pos),
r = t;
else
Split(t->r, t->r, r, pos - 1 - cnt(t->l)), l = t;
upd(t);
}
Основная часть
программы. Последовательно обрабатываем запросы.
scanf("%d\n",&n);
for(k = 0; k < n; k++)
{
scanf("%c %d %d\n",&c,&i,&j);
if (c == '+')
{
Split(t,t1,t2,i);
Merge(t1,new Item(j),t1);
Merge(t1,t2,t);
}
else
{
Split(t,t,t1,i-1);
Split(t1,t1,t2,j-i+1);
Разрезали
исходное дерево на три: t, t1, t2. Выводим минимум на дереве t1. После чего делаем склейку.
printf("%d\n",t1->Min);
Merge(t,t1,t);
Merge(t,t2,t);
}
}