We are given an array of size N with numbers 1 <= Ai <= N(not always distinct).

There are N queries (L, R, K). For each query we need to print amount of Ai <= K, L <= i <= R. N <= 2e5

I know how to solve this task using Mo's Algorithm and Segment Tree in O(N * sqrt(N) * log2(N)). Is there a faster solution?

This is the original task, I know, probably there is an easier solution to it, but I want to try to solve it this way.

Merge sort segment tree would process queries in log(n). You can easily find further information about it.

TooNewbie How is Merge sort segment tree Query in logN? Isn't it log^2N? Thanks.

Yes. My bad, it's log^2(n).

you can improve it to logN per query with fractional cascading, but somehow it doesn't result in better running times.

Wavelet tree is another option, and it's easy to implement

Can you link some material regarding logN per query with fractional cascading ? I am unable to find. Thank you.

suppose you want to merge 2 sorted arrays

`a`

and`b`

into`c`

. For each`x`

in`c`

, store triplet (`x`

, first`i`

such that`a[i]>=x`

, first`j`

such that`b[j]>=x`

).So, when answering queries, you will need only 1 binary search at the top level, and all other binary searches will be replaced with these O(1) transitions.

Persistent segment tree —

O(N*logN)Persistence Made Simple — Tutorial Persistent segment trees

I think it's , or you mean .

I meant base 2. Updated it to logN.

At first, I wrote

O(N*log2N*log2N), later on, converted it intoO(N*log2N)One simple soln in O(

N*log_{2}(N)) is using segment trees. Lets have segment tree which has two operations.1. Update some position(x) value to 1(initially all are 0).

2. Find the number of 1s in some range [l,r].

Then, sort the queries in order of

A_{i}. BeforeA_{i}query, make updates at position whose value is less than or equal toA_{i}. And then 2nd operation gives us the answer.You can also use BITs to decrease the constant factor of this solution.