2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 10:25 


07/04/14
10
Дана полоса из N клеток. На вход поступают запросы - закрасить клетку с номером $i$. Нужно определить после какого запроса есть x закрашенных подряд клеток. Например:
$N = 5, x = 3 $, красим клетки $1, 5, 4, 3, 2$ - после 3его запроса с 3 по 5ую клетку закрашены. Как можно решить эту задачу, не пробегая по массиву при каждом запросе? Как можно применить деревья отрезков для такой задачи?

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 11:15 


26/08/11
120
Можно решить с помощью RB-Tree. В качестве узлов храните полностью закрашенные подотрезки. У каждого подотрезка 2 параметра: $left$, $right$. В качестве компаратора используйте правую границу отрезка. На каждый запрос создаёте новый отрезок длиной $left = x$, $right=x$. За $O(\log n)$ можно находить наибольший узел строго меньший чем заданный и наименьший узел строго больший чем заданный. Найдя эти два узла, у вас возникает 3 ситуации: 1) либо новый подотрезок не касается найденных двух; 2) касается одного из них; 3) соединяет их. Зная параметры вы можете легко найти длину нового подотрезка и уже заключить появление подотрезка длиной $x$. Операции удаления, вставки также работают за $O(\log n)$.
В Java есть реализация RB-Tree. http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 11:44 


07/04/14
10
Спасибо, попробую закодить :D

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 13:42 


07/04/14
10
Guliashik в сообщении #848308 писал(а):
За $O(\log n)$ можно находить наибольший узел строго меньший чем заданный и наименьший узел строго больший чем заданный.

Как это можно реализовать на C++/Java? Не вижу способа это делать за $O(\log n)$...

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 13:46 


26/08/11
120
Если пользуетесь готовой реализацией, то существуют функции http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html#higher%28E%29 http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html#lower%28E%29

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 14:12 
Заслуженный участник
Аватара пользователя


09/02/14
1267
Нужно хранить два массива L[i],R[i] — ссылку на первого левого и последнего правого закрашенного элемента в подотрезке и после каждого запроса
(i) Обновлять массивы в клетке с номером $i$
(ii) Проверять условие $R[i]-L[i] \geqslant x$

-- 11.04.2014, 13:13 --

Ещё можно использовать DSU очевидным образом

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 14:36 


26/08/11
120
Ещё одно решение, гораздо легче предложенного мною ранее:
Если вам заранее известны все запросы и у вас только запросы покраски (нельзя стирать клетку), то просто будем делать бинарный поиск по ответу. При этом на каждом шаге, будем проверять, появился ли подотрезок длиной $x$. Очевидно что сложность $O(n \log n)$

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 15:01 


07/04/14
10
Guliashik в сообщении #848360 писал(а):
...просто будем делать бинарный поиск по ответу. При этом на каждом шаге, будем проверять, появился ли подотрезок длиной $x$

Хмм, а как можно проверить за $O(1)$, появился ли отрезок нужной длины?

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 15:03 
Заслуженный участник
Аватара пользователя


09/02/14
1267
Достаточно проверять за $O(N)$ чтобы добиться сложности $O(NlogN)$, а мои решения вам не понравились? :3

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 15:28 


07/04/14
10
kp9r4d в сообщении #848369 писал(а):
Достаточно проверять за $O(N)$ чтобы добиться сложности $O(NlogN)$, а мои решения вам не понравились? :3

А, я думал автор имел ввиду $O(M\log N)$, M - кол-во запросов.

Не совсем понятно ваше решение :-( , можете на примере объяснить?

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 15:52 
Заслуженный участник
Аватара пользователя


09/02/14
1267
Ну так-то имелось в виду скорее $(M+N)logM$ однако можно заметить, что «содержательных» запросов, то есть таких, которые что-то меняют может быть не более, чем $N$.

Я предлагаю следующее, представьте, что у вас есть отсортированный список натуральных чисел от 1 до N со следующим функционалом:
(del x) Удалить элемент, в котором записано число $x$ (если он есть)
(findR x) Найти наименьший элемент $y$ содержащийся в списке такой, что $y \geqslant x$, либо вернуть $N+1$, если такого не существует.
(findL x) Найти наибольший элемент $y$ содержащийся в списке такой, что $y \leqslant x$, либо вернуть $0$, если такого не существует.

Продемонстрирую команды на примере, пусть $N=6$
... → (1 2 3 4 5 6)
del 3 → (1 2 4 5 6)
del 4 → (1 2 5 6)
del 5 → (1 2 6)
findR 3 → 6
findR 4 → 6
findL 5 → 2
findL 2 → 2
del 1 → (2 6)
findL 1 → 0

Теперь вполне очевидно как имея такой список решить задачу.
Сперва инициализируем список от $1$ до $N$. После очередного запроса на закрашивание $i$ делаем $\operatorname{del} i$ и делаем проверку $(\operatorname{findR} i) - (\operatorname{findL} i) - 1 \geqslant x$, если она выполняется, то говорим, что на этом запросе как раз появился закрашенный отрезок длины $x$.

Я утверждаю, что такую структуру данных написать можно таким образом, чтобы все операции она выполняла амортизировано за $O(1)$ и, таким образом, всё решение будет за $O(N+M)$. Подумайте как, если не додумаетесь — напишите, я напишу решение.

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 16:34 


07/04/14
10
kp9r4d в сообщении #848388 писал(а):
Я утверждаю, что такую структуру данных написать можно таким образом, чтобы все операции она выполняла амортизировано за $O(1)$ и, таким образом, всё решение будет за $O(N+M)$. Подумайте как, если не додумаетесь — напишите, я напишу решение.

Алгоритм ясен :-) .
Ну пока мне понятно, как удалять за $O(1)$, и бинпоиском можно находить за $O(\log N)$. Расскажите, как находить за $O(1)$

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 17:09 
Заслуженный участник
Аватара пользователя


09/02/14
1267
milos в сообщении #848394 писал(а):
как удалять за $O(1)$, и бинпоиском можно находить за $O(\log N)$

Бинпоиском — в смысле честным или в каком-нибудь дереве хранить? Если честным, то мне не понятно, расскажите, если вам несложно будет.

Сам этот список будем хранить в трёх массивах
Код:
isDelete[0..N+1]
Left[1..N]
Right[1..N]

В массиве isDelete будет хранится 0, если элемент ещё не удалён и 1, если он уже удалён
В массиве Left[i] будет хранится
(i) значение самого правого неудаленного элемента
(ii) либо значение какого-нибудь удаленного элемента $j \leqslant i$
когда какой случай поясню позже.
В массиве $Right[i]$ аналогично, но $\leqslant$ меняется на $\geqslant$
Инициализируется структура так:
Код:
void init()
for(i=0..N+1)
   isDelete[i]=0;
   Left[i]=i;
   Right[i]=i;
isDelete[0]=isDelete[N+1]=1;

Процедура удаления
Код:
void del(i)
isDelete[i]=1;
Left[i] = Left[i-1];
Right[i] = Right[i+1];

Функции findL и findR выглядит так:
Код:
int FindL(i)
return Left[i] = (isDelete[i] == 0) ? i : FindL(Left[i]);
int FindR(i)
return Right[i] = (isDelete[i] == 0) ? i : FindR(Right[i]);

Сперва кажется, что алгоритм должен работать за $NM$ ведь рекурсия в худшем случае сделает $N$ самовызовов, однако нетрудно заметить, что $FindL$ и $FindR$ суммарно могут быть вызваны за $O(M)$ запросов $O(M)$ раз. Ведь после того, как мы «раскрутили» рекурсию на M шагов вглубь мы, фактически, «сжали» $M$ удаленных элементов в один. Таких «сжатий» не может произойти больше, чем $O(M)$ (так как у нас удаленных элементов всего $O(M)$). Идея очень похожа на ту, что используется в КМП-алгоритме, а также в DSU. Фактически это и есть «урезанная» версия DSU, так как весовые потенциалы именно в этой задаче нам, по сути, ни к чему.

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 17:20 


07/04/14
10
Ну так раз множество упорядоченное, то можно честный бинпоиск, разве нет?
Спасибо за помощь, кстати

 Профиль  
                  
 
 Re: Задача на деревья отрезков (наверное)
Сообщение11.04.2014, 17:25 
Заслуженный участник
Аватара пользователя


09/02/14
1267
milos в сообщении #848407 писал(а):
Ну так раз множество упорядоченное, то можно честный бинпоиск, разве нет?

Ну тут либо хранить список, и тогда бинпоиск делать нельзя, так как доступ к элементу за $O(N)$, либо делать массив, но тогда удалять за $O(1)$ нельзя. Можно попытаться кое-как объеденить, но будет тогда что-то либо похожее на то, что расписал я, либо что-то похожее на стандартный set. Вот мне и интересно было, что же вы придумали.
Да пожалуйста. :3

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group