Help solving this query problem

Правка en1, от NeverSayNever, 2018-07-01 23:00:59

Hi Coders,

I am trying to solve a problem but couldn't up with a better solution.

Problem Statement

Given an array A of N integers and Q queries where 1 ≤ Ai ≤ 100, 1 ≤ N ≤ 105 & 1 ≤ Q ≤ 105. Each query gives L and R(a subarray of array A). For each query find the minimum X such that AX > AL + X and L + X ≤ R.

I tried solving this problem but couldn't up with a solution better than Q × N. Any help to improve the complexity would be much appreciated.

Теги query, datastructure

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский NeverSayNever 2018-07-03 12:46:53 16
en3 Английский NeverSayNever 2018-07-03 00:18:13 4 Tiny change: 'X > A_{L+X}$ and $L+X \le R$.\n' -> 'X > A_{L+X-1}$ and $L+X-1 \le R$.\n'
en2 Английский NeverSayNever 2018-07-01 23:01:34 10
en1 Английский NeverSayNever 2018-07-01 23:00:59 553 Initial revision (published)