2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Задача на деревья отрезков (наверное)
Сообщение12.04.2014, 06:54 


01/12/11
997
milos в сообщении #848292 писал(а):
Дана полоса из N клеток. На вход поступают запросы - закрасить клетку с номером $i$. Нужно определить после какого запроса есть x закрашенных подряд клеток. Например:
$N = 5, x = 3 $, красим клетки $1, 5, 4, 3, 2$ - после 3его запроса с 3 по 5ую клетку закрашены. Как можно решить эту задачу, не пробегая по массиву при каждом запросе? Как можно применить деревья отрезков для такой задачи?

При очередном закрашивании может появиться только один новый , закрашенный интервал клеток. Чтобы его выявить достаточно просмотреть соседние клетки. Хранить интервалы можно в списке или массиве.

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


09/02/14
1292
Skeptic в сообщении #848553 писал(а):
При очередном закрашивании может появиться только один новый , закрашенный интервал клеток. Чтобы его выявить достаточно просмотреть соседние клетки. Хранить интервалы можно в списке или массиве.

А как его длину узнавать?

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


01/12/11
997
Надо перебрать окрашенные клетки в обе стороны и подсчитать их число. Окрашенный интервал можно записать парой значений (<начало интервала>,<длина интервала>).

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


09/02/14
1292
Ну так-то ненамного лучше полного моделирования выйдет. Ведь по сути если красить сначала клетку 1, потом 2, потом 3, ... То нам придётся выполнить $O(N)$ операций сравнения за запрос и асимптотика будет $O(NM)$, или я неправильно вашу идею понял?

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


01/12/11
997
При полном переборе найдутся все существующие интервалы, и дополнительно придётся среди них искать последний.

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


09/02/14
1292
Skeptic в сообщении #849461 писал(а):
При полном переборе найдутся все существующие интервалы, и дополнительно придётся среди них искать последний.

Последний интервал может «расти» в длине и, таким образом, проверка всех остальных интервалов начиная с какого-то шага начнёт быть пренебрежительно несущественна, по сравнению с вычислением длины последнего.

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


10/05/13
251
Воспользуйтесь SQRT-декомпозицией.
Она позволит обрабатывать запросы за время $O(\sqrt{n})$
Тем более она проста в реализации чем RB-tree или Дерево отрезков.

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

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



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

Сейчас этот форум просматривают: mihaild


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

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