FREQ2 - Most Frequent Value
You are given a sequence of n integers a0, a1 ... an-1. You are also given several queries consisting of indices i and j (0 ≤ i ≤ j ≤ n-1). For each query, determine the number of occurrences of the most frequent value among the integers ai ... aj.
Input
First line contains two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a0 ... an-1 (0 ≤ ai ≤ 100000, for each i ∈ {0 ... n-1}) separated by spaces. The following q lines contain one query each, consisting of two integers i and j (0 ≤ i ≤ j ≤ n-1), which indicates the boundary indices for the query.
Output
For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
Example
Input:
5 3
1 2 1 3 3
0 2
1 2
0 4 Output: 2
1
2
NOTE - This problem is similar to a problem Frequent values.
hide comments
soumyo001:
2022-12-19 20:59:39
can we use segment tree? |
|
tarun_28:
2021-07-22 08:47:52
Mo's algorithm + Frequency of frequency array:) |
|
harsha_1_2:
2020-04-19 09:16:51
I am maintaining an array (a) which stores the number of elements for each frequency i.e a[x] is the no of elements having frequency x. I am finding maximum x having a non-negative value using square root decomposition. Complexity is ((q+n)*sqrt(n)). Getting TLE!! Need help |
|
amrit5:
2020-04-18 18:14:00
wrong ans after testcase 9 mos+binary search : ( |
|
sagarthecoder:
2019-10-29 18:17:52
I solved it using MO_algorithm &( binary search for per query ).
|
|
huynhtuan71ti:
2019-08-31 18:02:49
Mo's algorithm and binary search -> AC |
|
DOT:
2018-08-01 21:30:34
Mo's Algorithm works. :) |
|
mahmud2690:
2017-07-30 15:13:41
Too strict time limit |
|
adityaghosh96:
2017-01-03 04:50:50
O(N * sqrt(N)) with scanf,printf |
|
erdenebayr_d:
2016-03-09 15:10:11
O(N * sqrt(N)) is passed |
Added by: | Dominik Gleich |
Date: | 2011-06-20 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | My own problem. |