[Segment Tree][SPOJ] FREQUENT

FREQUENT 

Here is the problem statement:

You are given a sequence of n integers a₁ , a₂ , ... , a_n 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 a_i , ... , a_j. 

Input Specification

The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a₁ , ... , a_n (-100000 ≤ a_i ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: a_i ≤ a_i+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.
The last test case is followed by a line containing a single 0.

Output Specification

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

My Solution:

This is a segment tree question. Not because it can only be done via a segment tree, but because I am trying to learn segment trees, and it's amongst the questions I'm practicing. 

So, IMO there are two things one should think about when using segment trees:

1. Merge

2. Update

Merge  here means that assuming you've your answer for the left and the right child of a node, how will you percolate the result up? What intermediate values must you store in the child nodes such that the current node's solution can be reached efficiently?

Update depends upon the context. Do you have a point update or a range update? How will you manage to update the values of the node efficiently for whole of the segtree?

So these are the things I thought.

So, let's say a node contains the maximum occurring number and it's count. Cool cool. Now how does it's parent benefit from this information? It'll have the max count of it's left and right children. Good. But is there any merging required here? That can only be possible if there is an element that is in both the left and the right child. That means that the element is at the right most part of the left child and the leftmost part of the right child. 

But we don't save this information! So let's save that too. The count of the leftmost and the rightmost element of the node. When we merge, we check these too, and update the max element and it's count accordingly.

Now just go till the top and enjoy.

There's no update so no worries. :)

Some elegant code

My code :/