【POJ3368】Frequent values（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

Sample Output

1

4

3

題目大意：給出一個非降數列，多次求[l,r]内衆數的出現次數。

題解：RMQ，水一發玩玩。每個位置記這個數字到現在為止出現了幾次，詢問時用RMQ查，兩邊不全的特判一下就好了。

代碼如下：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#define ll long long
#define inf 0x7f7f7f7f
#define N 100005
using namespace std;
int n,m,a[N],f[N],g[N][],s,t; 
void init()
{
    for(int i=;i<=n;i++) g[i][]=f[i];
    for(int j=;(<<j)<=n;j++)
    for(int i=;i-+(<<j)<=n;i++) g[i][j]=max(g[i][j-],g[i+(<<j>>)][j-]);
} 
int rmq(int l,int r)
{
    if(l>r) return ;
    int k=log2(r-l+);
    return max(g[l][k],g[r-(<<k)+][k]);
}
int main()
{
    while(~scanf("%d",&n) && n)
    {
        scanf("%d",&m);
        a[]=inf;
        for(int i=;i<=n;i++) 
        {
            scanf("%d",&a[i]);
            if(a[i]==a[i-]) f[i]=f[i-]+;
            else f[i]=;
        }
        init();
        for(int i=;i<=m;i++)
        {
            scanf("%d%d",&s,&t);
            int tmp=s;
            while(tmp<=t && a[tmp]==a[tmp-]) tmp++;
            printf("%d\n",max(tmp-s,rmq(tmp,t)));
        }
    }
    return ;
}