You need O((n + q) log n) to get AC, or something very close to that.

Try to only use one segment tree, that gives you any "dominant color" in an interval, for which you then check if it appears enough times in the interval. The solution is completely online.

An alternate solution is by using persistent segment trees. At a node if we have two subtrees with sum of frequencies as S₁ and S₂, our answer either exists in the subtree with greater sum or doesn't exist. This gets AC in O((N + Q) * logN).

There is a solution with but I describe the one.

Let occ(x, L, R) as a function that returns the number of i's such that L ≤ i < R and a_i = x. It's easy to implement, for each color like x, keep a vector of indexes that a_i = x then answer is lower_bound(vec[x].begin(), vec[x].end(), R) - lower_bound(vec[x].begin(), vec[x].end(), L).

Now use segment tree. Consider a node for segment [L, R), keep the color that appears in [L, R) strictly more than (R - L) / 2 in that range, if there is no color satisfies the condition, save -1 there.

It's easy to merge two nodes:

node merge(node L, node R){
    node ans;
    ans.l = a.l, ans.r = b.r;
    for(auto candidate : {a.ans, b.ans})
	if(occ(candidate, ans.l, ans.r) > (ans.r - ans.l) / 2)
	    ans.ans = candidate;
    return ans;
}

Here is my code : Link.

This problem can also be solved with a randomised algorithm. You can see my solution here. The details can be found out in the editorial of this problem on codechef which is a harder version of the above problem with point updates as well.