kashyap2108's blog

Spoj-Frequent Values
By kashyap2108, history, 10 years ago, In English

How to solve SPOJ-FREQUENT VALUES "http://www.spoj.com/problems/FREQUENT/" using segment tree?? I want to know what to store in the node of the tree?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Maximum answer in the interval, number of numbers that are equal to a[r] and number of numbers that are equal to a[l].

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Sure? What about 1 2 2 2 3 ?

    (edit: silly me)

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      Maybe you misunderstood what he said. The answer is among the three things he mentioned — maximum answer in the interval (excluding a[l] and a[r]), number of numbers that are equal to a[r] or number of numbers that are equal ot a[l].

      → Reply
»
10 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

"a1 , a2 , ... , an in non-decreasing order." This is the key to the solution . Also u need a frequency array and just adjust the queries .

→ Reply