k 선형 함수로 구성된 배열에서 V보다 작은 최대 값 검색

Question

질문 설명에서 명확성이 부족해서 죄송합니다.

Length $ n $ $ k $ 선형 하위 어레이로 구성된 배열이 있습니다. 우리는 $ [l, r] $ 의 연속적인 서브 어레이로 선형 하위 배열을 정의합니다. 여기서 $ a [i] - A [i-1]= C $ , 모든 $ l 에 대한 상수. (참고 : $ c $ 은 다른 하위 배열에 대해 다를 수 있습니다. 배열의 요소는 정수입니다.) 선형 하위 배관 은 disjoint가 아닙니다 (인접한 인접한 선형 서브 어레이의 모든 쌍 사이에는 하나의 요소 교차점이 있습니다). 예를 들어, [1,3,5,4,3,2]는 2 개의 선형 서브 어레이가있다 : [1,3,5] 및 [5,4,3,2]. [1,3,5,1,2,3]은 3 : [1,3,5], [5,1], [1,2,3]

$ v $ quied 값 $ v $ 보다 작은 최대 값에 대한 여러 쿼리를 찾고 싶습니다. o (k) $ 및 $ o (n) $ $ o (k ^ 2) $ 및 $ o (n) $ 전처리. (어레이가 이미 K / EM> 선형 하위 배열의 관점에서 이미 상수 C 및 각각의 서브 러 레이의 길이가 정렬 된 것으로 순서대로 주문 된 것으로 가정합니다. 따라서 앞에서 설명한대로 모든 선형 서브 어레이뿐만 아니라 모든 선형 서브 어레이뿐만 아니라 선형 상수 C 의 시작 및 끝점이있는 어레이가 주어진다. 그래서 하나는 첫 번째 장소.) 그렇지 않으면, 그렇게 할 수없는 증거 (공식 또는 아닙니다)는 인정 될 것입니다.

물론 균형 잡힌 이진 검색 트리 (BBST) 또는 단순히 정렬은 목적을 달성하지만 $ o (nlogn) $ 프리 프로세싱이 필요합니다. ...에 각 SubArray 내에서 가장 큰 유효한 값을 확인하면 $ o (k) $ 쿼리 당 $ o (k) $ 이 너무 많이 사용됩니다. 이 두 가지 모두를 결합 할 수 있습니다.

무작위 알고리즘은 항상 정답을 달성하고 평균적 인 경우에 충분히 빠르게 작동하는 한, 결정 론적 알고리즘이 선호되지만

모든 반응에 감사드립니다. 나는 그 질문에 어떤 연구가 있는지 궁금해하고 있었을 것입니다. 그것은 너무 모호한 것처럼 보이지 않지만 불행히도 내 검색은 충분히 유능하지 않았습니다.

편집 : 유용한 방법입니다.

여기에 물어 보낸 후 내 생각의 라인이있었습니다. 이것이 어떻게 든 도움이 될지 궁금합니다. 그것은 모듈로의 아이디어를 사용합니다. V=0를 초기화하고, 각 선형 서브 어레이를 L,R로 저장하도록 허용하는 단계; 여기서 L는 Subarray의 최소값이며 R가 최대 값입니다. V에 대한 쿼리가 주어지면, 우리는 L>V 및 R<V (아마도 다중 치수를 사용함으로써) 보충 데이터 구조가 L - V mod c[i]와 같은 어레이 내의 요소의 최소 이론적 인 차이를 저장하는 요소를 어떻게 억제한다. 본질적 으로이 데이터 구조에서 범위 추가를 실행할 필요가 있지만 모든 요소의 값이 <0 또는 >=c[i]가 될 경우 재설정 해야하는 경우 (예 : 요소가 C [i로 -1과 동일하게되는 경우) ]= 5는 4로 재설정 될 것입니다. 동일한 C [i]가 동일한 C [i]가 1로 재설정 될 수 있습니다. 또한 범위 최소 쿼리를 실행하십시오.

이러한 데이터 구조를 만들 수있는 경우 문제가 해결됩니다. 문제는 범위 추가 및 범위 최소 쿼리가 세그먼트 트리 및 게으른 전파로 쉽게 수행 할 수 있습니다. 특정 요소의 분리뿐만 아니라

Answer 1

쿼리 된 값 $ V $ 에서 $를 찾을 수 없음을 보증 할 수 없습니다. $ o (n) $ 시간에 전처리가있는 o (k) $ 시간.

다음과 같은 극단적 인 경우에는 쉽게 볼 수 있습니다. $ a $ 다음 $ n $ 정수의 배열이됩니다.="수학 용기"> $ k= n-1 $ 선형 서브 어레이.

• Subarray $ a [0], $ C= A [1] [0] $ .
• Subarray $ a [1], $ C= a [2] [1] $ .
• $ \ cdots $
• Subarray $ a [n-2], $ C= A [n-1] $ n-1] -a [n-2] $ .

$ o (n) $ 시간 전처리 및 $ o (k)= o (n) $ 시간 처리, 알고리즘은 $ N $ 은 충분히 크다. (실제로 $ a $ .)의 대부분의 숫자는 일부 쿼리 값 $ q $ 알고리즘은 $ q + 1 $ 이 $ a $ 에 나타납니다.

(예를 들어, 위의 설명은 더욱 엄격해질 수 있으며, 잘 정의 된 계산 모델을 사용하여 더 엄격하게 만들 수 있습니다.)

---

$ o (n \ log n) $ $ o (k) $ 쿼리 당. 또는 $ o (n) $ 사전 처리 및 $ o (k) $ 쿼리 당 $ k= o (n) $ 을 감안할 때. 어쨌든 다른 질문처럼 들리네.