Help solving this query problem

Revision en2, by NeverSayNever, 2018-07-01 23:01:34

Hi Coders,

I am trying to solve a problem but couldn't come 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 come up with a solution better than Q × N. Any help to improve the complexity would be much appreciated.

Tags query, datastructure

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English NeverSayNever 2018-07-03 12:46:53 16
en3 English 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 English NeverSayNever 2018-07-01 23:01:34 10
en1 English NeverSayNever 2018-07-01 23:00:59 553 Initial revision (published)