Spoj-Frequent values

You are given a sequence of n integers a1 , a2 , … , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , … , aj.
1 ≤ n, q ≤ 100000) and (-100000 ≤ ai ≤ 100000) !!

I’m trying to solve it using a segment tree but unable to find what to store in the node?


This one is directly from mho algorithm. You can read about this HERE.

As it’s offline query mho algorithm will be best but it will not be consider for online query where you need to use different data structure like segment tree.

If you really wanna solve from segment tree then there is one question which you can relate here. Codechef


read here
it has a very good tutorial of the problem along with other segment tree variations.

What will we do in case of online query? Any links? I am curious!! :slight_smile:

click on codechef link

@bansal1232 for offline too, a segment tree is required I guess.

@ankesh18 u can use segment tree for offline and online both. but mho is used only for offline query

Thanks dear !!

thanks bansal1232!!