Простой в реализации метод: держите отрезки в каждом элементе отсортированными и непересекающимеся (если два отрезка пересекаются - объедените их).
Далее при запросе пройдитесь по списку и для каждого элемента бинпоиском найдите самый правый отрезок, начало которого левее запроса. Проверьте, лежит ли запрос в отрезке. Это будет чуть быстрее наивного метода, но все-равно пройдется по многим элементам списка зря.
Если же список очень длинный, а ответ ожидается маленький, то есть более быстрый метод. Но он сложный в реализации. Нужно реализовать персистентное
дерево поиска. Можно его реализовать на основе персистентного
дерева отрезков. Это такая структура, в которую можно добавлять элементы, и удалять их за O(log n). Также можно обходить все элементы за O(log n + (их количество)). Кроме того, сохраняются все версии дерева после каждой операции и общее количество памяти будет O(к log n), где к - количество операций.
Эта структура будет использоватся для хранения предподсчитанных ответов. Если все ваши отрезки нарисовать на одной прямой, то она разобъется на O(n) отрезков, все точки которого будут давать один и тот же ответ при запросе. Мы эти все ответы компактно сохраним.
Используем метод сканирующей прямой. Нанесите все границы всех отрезков на одну прямую, пометив их как начало или конец (и какому элементу списка они соответствуют). Если пройтись по этой прямой слева на право, то будут происходить события - отрезки откроются (новый элемент добавляется в ответ) или отрезки закроются (элемент из ответа удалится). Поддерживая текущий ответ в персистентной структуре мы сильно экономим память. Удобно в качестве начал отрезка брать их координаты, а в качестве конца - координаты концов+1. В таком виде все границы отрезков будут точками, а не числами.
Итак, создайте массив из структур {координата, это начало или конец, номер элемента}. Отсортируйте по координате, потом по флагу начала. Потом пройдитесь по ней и при обработке начала отрезка - добавляйте номер элемента в персистентное дерево. При обработке конца - удаляйте элемент из дерева. Так же перед обработкой каждого элемента запишите в массив-ответ: {предыдущая координата, текущая координата, ссылка на текущую версию персистентного дерева}, если предыдущая координата строго меньше текущей. Этот массив-ответ будет хранить все возможные отрезки с различными наборами ответов в виде {координата начала, координата конца, ответ}.
Когда вы этот массив ответов предподсчитали, можно обрабатывать запросы - Найдите в массиве бинпоиском тот отрезок, которому текущая точка-запрос принадлежит. Вам надо бинпоиском найти самый правый отрезок, у которого начало меньше-равно числа-запроса. Потом проверьте, что координата конца строго больше запроса. В этом случае выводите в ответ обход персистентного дерева по известной версии.
Это решение требует O(n log n) памяти (где n - количество всех отрезков) и O(n log n) времени на предподсчет и O( log n + (ответ)) времени на обработку ответа.
Более простое решение, где ответы считаются так же сканирующей прямой, но сохраняются просто в виде списков, а не версий персистентного дерева, может требовать O(n^2) памяти. Но будет работать быстрее, конечно.
Простой
Простой
