### speedster's blog

By speedster, history, 9 years ago,

How to solve this: given multiple query of type : x l r , we need to find the frequency of x in the range r to l. There are no updation so basically calls out for an offline algorithm .

• +2

| Write comment?
 » 9 years ago, # | ← Rev. 3 →   0 I think it can be solved by Mo algorithmSort queries by this comp: bool comp(Query x, Query y) { if (x.l!=y.l) return x.l < y.l; return x.r < y.r; } Let freq[i] be the frequency of number i, you can now solve the problem by shifting the previous L,R query to the curL, curR and then answer the query.
•  » » 9 years ago, # ^ | ← Rev. 2 →   +4 What your comparing function does is not what Mo's algorithm is supposed to. You can't simply sort the queries as pairs and expect this to work fast. The correct function goes here: bool comp(Query x, Query y) { if (x.l/(int)(sqrt(n))!=y.l/(int)(sqrt(n))) return x.l < y.l; return x.r < y.r; } For example, if N=9 and there are queries (1,9), (2,4) and (3,6), then they should be in order (2,4), (3,6), (1,9) or (1,9), (3,6), (2,4) but your function will sort them like (1,9), (2,4), (3,6).
•  » » » 9 years ago, # ^ |   +3 Oh you're right, that was my mistake, thanks.
•  » » » 9 years ago, # ^ |   +3 I know this is probably just an example code but I want to point out that sqrt(n) would return a double, and most probably x.l / sqrt(n) will be converted to a double itself, so the "!=" comparison may not produce correct results.Use (int)sqrt(n) instead :)
•  » » » » 9 years ago, # ^ |   +11 Oh, that was a stupid mistake. I usually use int sq=sqrt(n); and then use sq in comparisons just because of that casting but this time I somehow forgot the (int), thanks for the correction! :)
 » 9 years ago, # |   +3 for each number in the input array, store the indices where it's present in a vector. for each query x l r, the answer will be upper_bound(r) — lower_bound(l).what is an offline algorithm?
 » 9 years ago, # | ← Rev. 2 →   0 sorting query with square-root decomposition gives O( n ^ 1.5 )There is online solution with O ( n lg ^ 2 n )first, store each step of merge sort such as3 1 4 1 5 9 2 6( 1 3 ) ( 1 4 ) ( 5 9 ) ( 2 6 ) ( 1 1 3 4 ) ( 2 5 6 9 ) ( 1 1 2 3 4 5 6 9 )then, [l, r] can be decomposed to O (log n) intervals with 2^k sizes. for example, [3, 6] (0-based, inclusive) can be decomposed to [3,3], [4, 5], [6, 6] you can add up all upper_bound(x) — lower_bound(x) for each interval and that is answer.