Задача Дан массив чисел, нужно быстро уметь отвечать на вопрос : есть ли на каком — то отрезке какое — то число.(Быстро — быстрее чем за O(длинны отрезка))
Из структур данных, позволяющих отвечать на какие то запросы на отрезках я знаю дерево отрезков, но я что то не могу придумать, как его здесь использовать.
Это задача с Тимуса http://acm.timus.ru/problem.aspx?space=1&num=1613, идет под темой Структуры данных.
Подскажите пожалуйста, какую структуру данных здесь надо исользовать?
Без 2d дерева отрезков точно можно обойтись. В принципе, достаточно просто отсортированного массива пар <количество, город>.
Основное наблюдение — нам нужно проверить, если ли во входных данных пара, совпадающая по количеству и лежащая в диапазоне по городу.
Минусуйте меня, торопыжка здесь я — не умею читать :-(
UPD: Мне правда стыдно, не надо плюсовать, минусуйте!
А bayleef выше плюсуйте, он всё правильно сказал!
Приходит на ум такое просто решение за O(q*sqrt(n)).
Краткое описание:
Ужмём координаты, теперь у нас числа до 70000.
Так как запросы даны сразу все, можем решать оффлайн, посортим запросы по паре (block(l), r). где block(l) — число, если l в (1..sqrt(n)) тогда 1, если (sqrt(n)..2*sqrt(n)) то 2. То есть номер блока длины sqrt(n) в который попадёт l. block(l)<=sqrt(n).
Тогда в массиве col[n] будем хранить сколько на текущем отрезке (l..r) чисел n. Переходя от одного запроса к другому будем в лоб двигать правую и левую границу, пересчитывая массив col.
( Доказывается, что время будет q*sqrt(n), это очень-очень известный приём, его док-во и подробное объяснение, вроде, можно увидеть и в лекции Бурундука. )
Надеюсь, что будут меньше минусовать :)
Вот код:http://pastebin.com/FnRKRqMj
Не очень красивый, но пояснения:
a — исходный массив, ans — будем ответ хранить, сol — массив, который поддерживаем, q — массив с запросами, p — перестановка запросов ( чтобы знать их отсортированный порядок, но их самих не менять местами ). bl — размер блока ( для сорта, = (int)(sqrt(n)) ). so — массив для всех чисел, с его помощью ужмём. comp — компаратор.
Строчки:
68-71 — ужатие координат
потом сорт запросов и проход по ним. Всё!
Если есть вопросы, обращайтесь.
Отработало на тимусе за 0.234.
http://www.youtube.com/watch?v=f6L8ZucH-0M
Вот, кстати, та лекция о которой я говорил. Этот приём начинается на 55 минуте. Но лучше посмотрите всю лекцию, она полезная.
Почитай эту статью на e-maxx. Очень поможет. В конце статьи описано как подобные задачи решать. http://e-maxx.ru/algo/sqrt_decomposition
Сжатие координат + бинпоиск : http://pastebin.com/hzWPinSS
Я просто отсортировал массив пар (кол-во, город) по возрастанию. На каждый вопрос двумя бинпоисками находил левую и правую границу пар, число перевезенных пассажиров у которых совпадает с запрошенным числом v. И третьим бинпоиском я находил среди получившихся пар такую, у которой номер города больше или равен l, а также меньше или равен r
Мое решение не самое оптимальное, но все же. Построим дерево отрезков, в каждой вершине которого будет храниться отсортированный подотрезок. Отвечаем на запрос за квадрат логарифма: если текущий отрезок полностью лежит в том, который запрашивали делаем в нем бинописк.
Давний код, если что, могу переписать.
UPD: Тот же код, только лучше написанный: link.
Я разбивал массив на sqrt(n) блоков и делал в них бинпоиски. На Java зашло за 0.7 секунд. Да, это q*sqrt(n)*log(n).
Сжатие координат, потом для каждого числа сохранять список позиций.
Каждый запрос обрабатывается так:
Сначала проверяем есть ли число вообще, если оно есть то бин-поиском по всем позициям :)
А можно сканлайном. Идем от 1 до N и для каждого числа храним его самое правое вхождение. Потом если попадается правая граница какого-то запроса — просто смотрим, лежит ли самое правое вхождение числа запроса после l.