Help to understand "Easy Query" solution

Problems and Contests
#1

I got stuck on the “Easy Query” problem for some time now. I understand the 1st step which is to use a wavelet tree to identify the su and sv for each query, but I got TLE error when using segment tree to do the (offline) query list.

My segment tree is basically based on the unique value of ai (of course, using value compression as well). The query is sorted by left edge and then by right edge. When moving from one query to another, I remove ai that is not in the (new) query and add ones’ missing. I think this is where the TLE happens since worse case is O(n*n)

Reading BenQ’s internal solution, I could not figure out how the segment tree update is done to speed up. It seems to use binary jump, but I could not really understand it. Any further hint/explaination would be highly appreciated.

#2

not sure where you got this from. I have a loop from 0 to 30-1 because I compute each of the 30 bits of f(t^i) independently. The k-th bit of f(t^i) is equal to 1 if there exists some value x such that the following conditions hold:

  • x\in [s_u+1,s_v-1]
  • the k-th bit of x is one
  • the i-th leftmost occurrence of x among a_{\ell},\ldots,a_n is less than or equal to r. (a[k] <= t[0] in the code)

The indices of each segment tree correspond to the x that appear in a_i in increasing order. Each node of the i-th segment tree corresponding to some x-range [x_l,x_r], and stores the minimum j such that a_j is the i-th occurrence of x among a_{\ell},\ldots,a_n for some x\in [x_l,x_r].

Time is proportional to 30(n+q)\log n.