Найдите максимальное значение меньше V в массиве, состоящем из K линейных функций.

Question

Извините за неясность описания вопроса.

У меня есть массив, состоящий из длины $Н$ состоит из $К$ линейные подмассивы.Мы определяем линейный подмассив как непрерывный подмассив массива $[л,р]$ где $A[i]-A[i-1] = C$, константа для всех $l<i<=r$.(Примечание: $C$ может быть разным для разных подмассивов;элементы массива являются целыми числами.) Обратите внимание, что линейные подмассивы не являются непересекающимися (между любой парой соседних линейных подмассивов существует один элемент пересечения).Например, [1,3,5,4,3,2] имеет два линейных подмассива:[1,3,5] и [5,4,3,2].[1,3,5,1,2,3] будет иметь три:[1,3,5], [5,1], [1,2,3].

Я хочу найти несколько запросов для максимального значения, меньшего запрошенного значения. $В$, в $о(К)$ и $о(N)$ время на запрос, с $о(К^2)$ и $о(N)$ предварительная обработка.(Предположим, что массив уже сохранен в терминах К линейные подмассивы, возможно, в терминах константы С и длина каждого подмассива с упорядоченными подмассивами.Таким образом, вам дан массив с начальной и конечной точками всех линейных подмассивов, а также линейная константа С, как описано ранее.Таким образом, вообще не нужно выводить линейные подмассивы.) В противном случае было бы полезно доказать (формальное или нет), что это невозможно.

Конечно, сбалансированное двоичное дерево поиска (BBST) или просто сортировка достигают цели, но для этого требуется $O(NlogN)$ предварительная обработка, а это слишком много.Проверка наибольшего допустимого значения в каждом подмассиве занимает $О(К)$ за запрос, что опять-таки слишком много.Возможно ли что-то объединить и то, и другое?

Рандомизированные алгоритмы хороши, если они всегда дают правильный ответ и работают достаточно быстро в среднем случае, хотя детерминированные алгоритмы предпочтительнее.

Спасибо за любые ответы.Мне было интересно, возможно, проводились ли какие-либо исследования по этому вопросу?Вроде бы не такая уж и неясная тема, но, к сожалению, мои поиски оказались недостаточно компетентными.

РЕДАКТИРОВАТЬ:Метод, который кажется полезным.

Вот мои мысли после того, как я задал вопрос;Интересно, поможет ли это как-нибудь.Он также использует идею модуля.Инициализировать V=0, и разрешить сохранение каждого линейного подмассива как L,R;где L - минимальное значение подмассива и R является максимальным значением.Когда нам дан запрос на V, мы каким-то образом исключаем элементы, где L>V и R<V (возможно, используя несколько измерений?) Дополнительная структура данных хранит минимальную теоретическую разницу элемента в массиве, что-то вроде L - V mod c[i].По сути, теперь нам нужно иметь возможность запускать добавление диапазона к этой структуре данных, но если значение любого элемента становится <0 или >=c[i] его необходимо сбросить (например.если элемент становится равным -1 с c[i]=5, он будет сброшен до 4;если элемент станет равным 6 с тем же самым c[i] будет сброшен до 1);а также запускать запросы минимального диапазона.

Если такую ​​структуру данных можно создать, проблема решена.Проблема в том, что по модулю, поскольку запрос на добавление диапазона и минимальный диапазон можно легко выполнить с помощью дерева сегментов и ленивого распространения;а также исключение некоторых элементов.

Answer 1

Невозможно гарантировать нахождение максимального значения, меньшего запрошенного значения. $В$ в $о(К)$ время с предварительной обработкой в $о(N)$ время.

В этом легко убедиться в следующем крайнем случае.Позволять $А$ быть любым массивом $Н$ целые числа, которые состоят из следующих $K=N-1$ линейные подмассивы.

• подмассив $А[0], А[1]$ с $C=A[1]-A[0]$.
• подмассив $А[1], А[2]$ с $C=A[2]-A[1]$.
• $\cdots$
• подмассив $А[N-2], А[N-1]$ с $C=A[N-1]-A[N-2]$.

С $о(N)$ предварительная обработка времени и $о(К)=о(N)$ обработки времени алгоритм не сможет даже прочитать некоторое число в $А$ когда $Н$ достаточно велик.(На самом деле, большинство чисел в $А$.) Итак, для некоторого запрошенного значения $q$, алгоритм не сможет распознать, что $q+1$ появляется в $А$.

(Приведенное выше объяснение можно было бы сделать более строгим, например, используя формальный метод противника и четко определенную модель вычислений.)

---

Похоже, что более интересный вопрос заключается в том, существует ли алгоритм с $o(N\log N)$ предварительная обработка и $о(К)$ за каждый запрос.Или есть ли алгоритм с $о(N)$ предварительная обработка и $о(К)$ за заданный запрос $K=o(N)$.В любом случае, это звучит как еще один вопрос.