首页 > 代码库 > poj 3368（RMQ简单应用）

poj 3368（RMQ简单应用）

2024-07-18 03:33:12   219人阅读

Frequent values
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 13317 Accepted: 4894

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

Source

Ulm Local 2007

详细参考刘汝佳的算法训练指南第198页，看了就懂了。

AC代码：

#include<stdio.h>
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[100010];
int val[100010],counter[100010];
int num[100010],Left[100010],Right[100010];
int d[100100][110];
int n,q;
void RMQ_init(){
    int i,j,k;
    int tmp;
    val[1]=a[1];
    k=num[1]=Left[1]=1;
    for(i=2;i<=n;i++){
        if(a[i]!=val[k]){
            Right[k]=i-1;
            counter[k]=Right[k]-Left[k]+1;
            k++;
            Left[k]=i;
            val[k]=a[i];
        }
        num[i]=k;
    }
    Right[k]=n;
    counter[k]=Right[k]-Left[k]+1;

    for(i=1;i<=k;i++)
        d[i][0]=counter[i];
    for(j=1;(1<<j)<=k;j++)
    for(i=1;i+(1<<j)-1<=k;i++){
        d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
    }


}
int RMQ(int x,int y){
    int k=0;
    while((1<<(k+1))<=y-x+1) k++;
    return max(d[x][k],d[y-(1<<k)+1][k]);
}
int main(){
    while(scanf("%d",&n)!=EOF){
        if(n==0)
            break;
        scanf("%d",&q);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        RMQ_init();
        while(q--){
            int x,y;
            scanf("%d%d",&x,&y);
            if(num[x]==num[y]){
                printf("%d\n",y-x+1);
            }
            else{
                int ans;
                ans=max(Right[num[x]]-x+1,y-Left[num[y]]+1);
                if(num[x]+1<=num[y]-1){
                    ans=max(ans,RMQ(num[x]+1,num[y]-1));
                }
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}



联系
我们