범위 쿼리 : 배열 A의 인덱스 범위 [1 : r]에 X보다 크고 Y보다 작은 최대 요소 X

Question

양의 정수 및 일부 쿼리의 배열 A가 제공됩니다.

각 쿼리에는 양의 정수 X, Y, l 및 r이 제공됩니다.

각 쿼리에 대해 배열 A의 범위 [1 : r]에서 X보다 크고 Y보다 작은 최대 요소를 찾아야합니다. 이러한 요소가 없으면 -1을 출력합니다.

나는 배열의 범위에서 K보다 작은 최대 원소를 찾을 수있는 유사한 질문에 대한 설명을 가지고 있습니다. 하지만 여기서 나는 그 논리를 적용 할 수 없다.

기대되는 시간은 O (log n) 또는 폴리 로그 시간입니다.

Answer 1

힙 데이터 구조가 필요합니다. 그러나 나는 항상 Big O 대신 물결표 표기법을 사용하여 timecomplexity를 지적했습니다. 따라서 N 항목을 사용하는 힙 데이터 구조는 ~ 1 + logN 이상을 취하지 않아서 제거 ~ 2logN을 사용하고 큰 O를 사용하면 O와 같습니다 LogN).

Answer 2

I had an explanation of similar question where you are to find the maximum element less than K in a range of array. But here I am not able to apply that logic.

나는 당신의 설명을 모른다. 하지만 당신이 그걸 만들 수 있다고 생각합니다.

논리를 적용한 결과 최대 요소가 Y 미만인 것으로 가정합니다. 최대 요소는 u (-1 if no such value)으로합시다.

if (u > X) 
{ 
    return u; 
} 
else 
{ 
    return -1; 
}