ACM/ICPC RMQ

POJ 3368 Frequent values 解题报告

dianlujitao 无回复
Time Limit: 2000MS Memory Limit: 65536KB 64bit IO Format: %lld & %llu

Description

You are given a sequence of n integers a1 , a2 , … , an 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 ai , … , aj.

Input

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 a1 , … , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, …, n}) separated by spaces. You can assume that for each i ∈ {1, …, n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i andj (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

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

Sample Input

Sample Output

Source


题目大意为给出一个n个数的不下降数列,然后有q个询问,求给定区间内出现最多的数的次数。由于数列是不下降的,相同的数必然挨在一起,这个数列边自然分成了若干块,并且每块中的数都相等。令f[n]为第n个数在块中的编号,如样例f[1]=1, f[2]=2, f[3]=1, f[4]=2, f[5]=3……

预处理完成后考虑一种特殊情况,如果询问给定的区间的左端点恰好是一个块的左端点的话,对f数组用RMQ求区间最大值即可。回到一般情况,左端点在一个块的中间怎么办?直接从左端点开始往右扫到下一个块为止,剩余部分便是特殊情况,RMQ解决,然后跟左边的比较,取最大值即为答案。
AC代码:

 



来一发吐槽