Задача на деревья отрезков (наверное)

[milos]

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

[Guliashik]

Можно решить с помощью 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

[milos]

Спасибо, попробую закодить

[milos]

Guliashik в сообщении #848308 писал(а):

За $O(\log n)$ можно находить наибольший узел строго меньший чем заданный и наименьший узел строго больший чем заданный.

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

[Guliashik]

Если пользуетесь готовой реализацией, то существуют функции 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

[kp9r4d]

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

-- 11.04.2014, 13:13 --

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

[Guliashik]

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

[milos]

Guliashik в сообщении #848360 писал(а):

...просто будем делать бинарный поиск по ответу. При этом на каждом шаге, будем проверять, появился ли подотрезок длиной $x$

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

[kp9r4d]

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

[milos]

kp9r4d в сообщении #848369 писал(а):

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

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

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

[kp9r4d]

Ну так-то имелось в виду скорее $(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)$. Подумайте как, если не додумаетесь — напишите, я напишу решение.

[milos]

kp9r4d в сообщении #848388 писал(а):

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

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

[kp9r4d]

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, так как весовые потенциалы именно в этой задаче нам, по сути, ни к чему.

[milos]

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

[kp9r4d]

milos в сообщении #848407 писал(а):

Ну так раз множество упорядоченное, то можно честный бинпоиск, разве нет?

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