Мне очень интересно, умеют ли сейчас люди решать вот такую задачу (я приведу сперва основную идею, а потом несколько вариаций условия):
Дана плоскость т.е. бесконечный грид точек с целыми координатами. На плоскость упали по очереди N прямоугольников (по очереди, значит, порядок важен) со сторонами параллельными осям координат и значением valuei внутри. Для всех точек, покрытых прямоугольником, нужно сделать некоторую операцию с valuei. После этого вам поступают K запросов вида "посчитайте что-нибудь на прямоугольнике".
Предполагается, что структуру данных для N прямоугольников можно строить в Offline, а вот на запросы нужно отвечать в Online.
- операция +=, запрос сумма
- операция +=, запрос минимум
- операция присваивание, запрос сумма
- операция присваивание, запрос минимум
Утверждается, что я умею решать все 4 задачи за следующее время:
- Time = Nlog, Memory = Nlog, AnswerQuery = log
- Time = Nlog2, Memory = Nlog2, AnswerQuery = log
- Time = Nlog2, Memory = Nlog, AnswerQuery = log
- Time = Nlog3, Memory = Nlog2, AnswerQuery = log
Краткое описание решений:
- 1-я задача: Scanline + Persistent Дерево Отрезков
- 2-я задача: Давайте для каждого K для каждого X-а предподсчитаем дерево отрезков по Y для полоски [X..X+2K) делается это опять же ScanLine-ом с Persistent Деревом Отрезков.
- 3-я задача: Scanline + Persistent Дерево Отрезков, при этом на дереве отрезков операция сложнее. Нужно добавлять и удалять информацию вида "на отрезок [L..R] в момент времени t кто-то упал", и, считая сумму на отрезке, выбирать последнее по t событие для каждой точки. Утверждается (1) если нет удаления, добавлять не трудно, (2) удалять не нужно. От удаления я избавляюсь также, как и в Dynamic-Connectivity в Offline, далее ссылка на условие задачи: http://195.19.228.2/Sk1/download/codeforces/connect.pdf
- 4-я задача: 2+3
UPD про задачи (2 и 3):
Я извиняюсь перед теми, кто видел первую версию поста. "Краткие решения" к задачам 2 и 3 были перепутаны местами =(
Не совсем понял задачу. Нам еще вначале дополнительно даны точки с их value или они как-то связаны с прямоугольниками?
Точек нет. Вернее так, в каждой целой точке плоскости (x,y) находится точка.
Есть прямоугольники. Значение valuei говорит нам, например, что нужно сделать += valuei на всем прямоугольнике.
Так понятнее получилось? :-)
Что делать, если два прямоугольника имеют общие точки?
А как это мешает хоть какому-то решению?
Дело не в том, что мешает/не мешает, а в непонимании условия. Например, у нас есть прямоугольник (0,0, 3,3) со значением 1 и (1,1,4,4) со значением 2. Что будет в точке (2,2)?
(1,1,4,4) был последним, значит будет значение 2.
Паш, кстати, а ты понял мои решения? А лучше умеешь? :-)
1,3 да. Как получается 4 из 2 и 3 тоже. А вот 2 ты как-то очень странно написал. "и, считая сумму на отрезке, выбирать последнее по t событие для каждой точки" Что ты имеешь ввиду я не понял. Да и как ты тогда избавился от удаления я тоже в ПТЗ не осознал.
По поводу лучше видимо нет, по модулю того что есть большое ощущение что корень квдрадеревом часто будет быстрее.
Сейчас сделаю UPD к посту про (2).
Да, расскажи, пожалуйста, про квадро-дерево. Как оно помогает ответить на такие запросы?
А почему мне казалось что оно умеет делать на плоскости почти любые запросы.. Или ты хочешь сказать, что мне надо будет знать начальные точки, а без этого я могу только за координаты им отвечать?
Если у нас есть N точек на плоскости, то КД-дерево — это структура аналогичная дереву отрезков на массиве длины N. Если у нас есть просто вся плоскость.. то непонятно.
Ну я про структуру, вроде той, котрая умеет искать площади фигур и.т.д. Правда в данном случае она будет работать за время, которое конечно порядка корня, но корня из суммарной площади прямоугольников.
Я вообще запутался что вы называете квадродеревом, но видимо две разные фиговины, можно в двух словах описать их устройство-быстродействие?
Или скажите к какому типу относится вот такая фиговина, описанная в моем комментарии.
Я имею ввиду конструкцию построенную на плоскости следующим образом. Изначально плоскость это один большой квадрат. Когда нам вдруг надо с квадратом сделать что-то не полностью бьем его на 4 части и радуемся. Это работает за время порядка суммарной длины границы запросов. Burunduk1 говорит об аналогичной структуре построенной на множестве точек. Работает она за корень от количества запросов, но все запросы нужны заранее.
Спасибо. То на что я дал ссылку, работает за квадрат логарифма. Это двумерное дерево отрезков построенное по заранее известным точкам запросов.
Okay:(
Ну, кстати, в третьем пункте надо обойти то, что координаты запросов заранее неизвестны. Нужно еще заметить, что между интересными Х координатами у нас сумма в прямоугольнике изменяется линейно, так что можно посчитать для X и X + 1, найти изменение за 1 шаг и затем посчитать его для нашего искомого прямоугольника.
Да, ты прав. Я забыл сказать, что функция, хранящаяся в дереве отрезков = A*x + B
А как нам во втором пункте поможет одно персистентное дерево? В случае суммы понятно — берем сумму на правом конце и отнимаем сумму на левом. А с минимумом как?
Сейчас сделаю UPD к посту.
А я все равно не верю, что 2 и 4 не log^2 на запрос.
Sparse Table же дает O(1) На запрос? Тут та же идея, отрезок [L..R] покрывается 2-мя отрезками длины 2^k, для которых уже все посчитано.
Так.. вопрос снимается..
Я правильно понимаю, что чтобы избавиться от удаления в Dynamic-Connectivity надо разделяй и властвуй по запросам делать?
Да :-) Я, правда, обычно это называю не "разделяй и властвуй", а "дерево отрезков". Наверное, потому что там нужно только разделить отрезок запросов на два.
А можешь немного подробнее рассказать решение хотя бы первой задачи? (что такое scanline и персистентное дерево рассказывать не надо :-))
Да, давай.
Сумма на прямоугольнике [x1..x2] x [y1..y2] = Sum(x2, [y1..y2]) — Sum(x1-1, [y1..y2])
Теперь нужно только для каждого x построить дерево отрезков по Y c операцией сумма. А Tree[x+1] получается из Tree[x] обработкой некоторых событий.
Если предположить, что все X-ы и Y-ки от 0 до 10^6, то решение уже готово. На самом деле, теперь нужно еще подумать про сжатие координат. Сжатие координат придется делать только по прямоугольникам-операциям, прямоугольников-запросов на этот момент мы еще не знаем. Чтобы теперь посчитать Sum(x, [y1..y2]) берем дерево Tree[x'] где x' — ближайшая к X-у точка, для которой у нас есть дерево. И говорим, что на [x'..x] сумма менялась линейно, а значит ее можно посчитать.
Мне кажется, третий пункт можно проще решать. Если в вершинах дерева отрезков хранить не только сумму, но еще и сет всех отрезков, отсортированный по t. Главное заметить, что этот сет персистентным делать не нужно, достаточно сохранять только сумму. Асимптотика, правда, не изменится.
А операцию "удаление" ты при этом делаешь? или, как и я, аккуратно от нее избавляешься?)
Делаю. Когда надо удалить отрезок, рекурсивно спускаюсь к нужным вершинам, удаляю прямоугольник из их сетов, а затем при подъеме обновляю суммы.
Я не умею пересчитывать сумму после удаления =( После одного удаления из массива 1 1 1 1 1 1 мог получиться массив 2 3 4 5 6 7...
Хм, действительно, сумму сразу обновлять не выйдет. Но можно просто хранить для каждой вершины сет и в дереве для каждой вершины помнить номер самого последнего отрезка, который ее накрывает.
Как тогда найти сумму в поддереве? Перебрать все листки из поддерева, для каждого найти номер самого последнего отрезка, который его накрывает (максимум на пути от корня) и прибавить к значению число, соответствующее этому отрезку. Это, понятно, работает долго.
Но, поскольку мы все делаем в оффлайне, можно уже после построения персистентного дерева, пройти по всем отрезкам в порядке убывания t, для очередного его значения (t0) найти все вершины, где максимум равен t0 и запустить бфс вниз, изменяя максимум у всех достижимых вершин на t0. Разумеется, если зашли в вершину с бОльшим максимумом, то дальше идти не следует. После этого можно рекурсивно просчитать значение суммы на отрезке во всех вершинах.