Help needed in getting A/C in frequent values problem from spoj?

general
, , , ,
1

Problem link :- FREQUENT - Frequent values

This is My Solution, I am getting TLE even after using fast I/o, anyone please help me in getting TLE in this problem. The problem is based on segment tree.

Thanks in advance

2

@vikram91 @rs_710 @purendra_ @hemanth_1 @shraeyas @vidyut_1 @aryanc403 @meooow @alexthelemon @vijju123 @ram_24 @harrypotter0 @pankaj_chopra @algmyr guys please help.

3

@vivek_1998299

Can you please help me with this, I have tried this a lot.

Thanks in advance

4

@abdullah768 @vijju123 @anjn98 @meooow @vikram91 @algmyr

Guys please help

5

Whats your approach?

6

@vivek_1998299

My approach :-

For any query if a[L]=a[R], then answer will simply be R-L+1.

if a[L]!=a[R] then and elements at L AND/OR R spill outside the segment then answer will be

max{
    count of element at L inside the range, 
    count of element at R inside the range, 
    Maximum frequency excluding elements at both the 
}

Suppose elements are 2 2 2 2 3 3 3 4 4 4 4 4 then frequency array will be, 4 4 4 4 3 3 3 5 5 5 5 5 and range is [3,8] here some 4 and some 5 are outside the range answer will be

max{
  no. of 2 inside [3,8] which is 2
  no. of 4 inside [3,8] which is 2
  maximum frequency count in range [5,7] 3
}

In my solution each node of the segment tree represents the maximum frequency count in that range.

I hope this make sense, ask me if still have doubts.