HDU-1806: Frequent values（RMQ）

RMQ

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 and j (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

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

Sample Output

1
4
3

题意：输入n，q，然后输入n个数字，q次询问，每次询问一个区间[st,en]中出现最多的数字出现的次数。

分析：由于原数列已经排好序，所以相同的数字一定是在一起的。我们可以O(n)扫描一遍，算出每一个位置上的数字num是从左起第几个num，记为num[i]；

如样例，扫描后如下，括号内是num数组值
-1(1) -1(2) 1(1) 1(2) 1(3) 1(4) 3(1) 10(1) 10(2) 10(3)

这样似乎直接求num数组区间[l,r]内的最大值就能得到答案。实际上这样无法得到正确的结果，因为如果查询区间左端点上num值不等于1，就会得到错误的答案。如对样例求[5,7]会得到4。

出现这个错误的原因上面已经说了，因为num数组是对区间[1,n]的计数。

解决方法也很简单，在O(n)倒着扫一遍，对于每个位置上的数字num，求出最右侧的数字为num的位置，记为R[i]，如下

-1(2) -1(2) 1(6) 1(6) 1(6) 1(6) 3(7) 10(10) 10(10) 10(10)

这样查询[l,r]时，只要R[l]

当R[l] >= r时，显然[l, r]整个区间都是同一个数字。答案为r-l+1

• 完整代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[100005],dp1[100005],dp2[100005],dpmax[100005][17];
int main()
{
    int n,q,i,st,en,d,j;
    while(scanf("%d",&n),n)
    {
        scanf("%d",&q);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        dp1[0]=0,dp1[1]=1;
        for(i=2;i<=n;i++)
        {
            if(a[i]==a[i-1])
                dp1[i]=dp1[i-1]+1;
            else
                dp1[i]=1;
        }
        dp2[n]=n;
        for(i=n-1;i>0;i--)
        {
            if(a[i]==a[i+1])
                dp2[i]=dp2[i+1];
            else
                dp2[i]=i;
        }
        /*for(i=1;i<=n;i++)
            printf("%d ",dp2[i]);*/
        for(i=1;i<=n;i++)
            dpmax[i][0]=dp1[i];
        for(i=1;(1<<i)<=n;i++)
            for(j=1;j+(1<<i)-1<=n;j++)
        {
            dpmax[j][i]=max(dpmax[j][i-1],dpmax[j+(1<<i-1)][i-1]);
        }
        while(q--)
        {
            scanf("%d%d",&st,&en);
            if(st>en)
                swap(st,en);
            if(dp2[st]>=en) //整个区间都是同一个数字
                printf("%d\n",en-st+1);
            else //查询区间[dp2[st]+1,en]上的最大值,和[st,dp2[st]]区间的值:dp2[st]-st+1进行比较
            {
                d=0;
                while((1<<d+1)<=en-dp2[st])
                    d++;
                printf("%d\n",max(max(dpmax[dp2[st]+1][d],dpmax[en-(1<<d)+1][d]),dp2[st]-st+1));
            }
        }
    }
    return 0;
}