[poj3368]Frequent values

Time Limit: 2000MS

Memory Limit: 65536K

分數：2100，小思維題

Description

You are given a sequence of n integers a 1 , a 2 , . . . , a n a_1 , a_2 , ... , a_n a1​,a2​,...,an​ in non-decreasing order. In addition to that, you are given several queries consisting of indices i i i and j ( 1 ≤ i ≤ j ≤ n ) j (1 ≤ i ≤ j ≤ n) j(1≤i≤j≤n). For each query, determine the most frequent value among the integers a i , . . . , a j a_i , ... , a_j ai​,...,aj​.

Input

The input consists of several test cases. Each test case starts with a line containing two integers n n n and q ( 1 ≤ n , q ≤ 100000 ) q (1 ≤ n, q ≤ 100000) q(1≤n,q≤100000). The next line contains n n n integers a 1 , . . . , a n ( − 100000 ≤ a i ≤ 100000 a_1 , ... , a_n (-100000 ≤ ai ≤ 100000 a1​,...,an​(−100000≤ai≤100000, for each i ∈ 1 , . . . , n ) i ∈ {1, ..., n}) i∈1,...,n) separated by spaces. You can assume that for each i ∈ 1 , . . . , n − 1 : a i ≤ a i + 1 i ∈ {1, ..., n-1}: a_i ≤ a_{i+1} i∈1,...,n−1:ai​≤ai+1​. The following q q q lines contain one query each, consisting of two integers i i i and j ( 1 ≤ i ≤ j ≤ n ) j (1 ≤ i ≤ j ≤ n) 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 u m [ i ] num[i] num[i]表示與 a [ i ] a[i] a[i]相同的 a [ j ] ( j &lt; = i ) a[j](j&lt;=i) a[j](j<=i)有多少個。

然後對于一個區間來說，如果這個區間的開頭的 n u m [ i ] num[i] num[i]是 1 1 1我們可以直接查詢這個區間的 n u m [ i ] num[i] num[i]的最大值作為答案，否則的話我們可以找到這個區間最靠前面的 1 1 1，然後，把這個區間分成從這個 1 1 1開始往後的，和這個 1 1 1之前的，之前的可以直接用 n u m [ i ] num[i] num[i]相減得到，後面的可以用st表查詢區間最大值，最後取最大值即可。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define INF 1999122700
using namespace std;
int mm[100004],a[100004];
int f[100004][24],g[100004][24];
int n,q,num[100004];
void prework(){
    mm[0]=-1;
    for(int i=1;i<=n;i++){
        mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
    }
    for(int j=0;j<=mm[n];j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            if(j==0){
                f[i][j]=num[i];
                g[i][j]=(num[i]==1)?i:INF;
            }
            else{
                f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
                g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
            }
        }
    }
}
int query(int x,int y){
    int k=mm[y-x+1];
    int l,r=y;
    l=min(g[x][k],g[y-(1<<k)+1][k]);
    if(l==INF)l=y+1;
    int ret=num[l-1]-num[x-1];
    if(l>r)return ret;
    k=mm[r-l+1];
    ret=max(ret,max(f[l][k],f[r-(1<<k)+1][k]));
    return ret;

}
int w33ha(){
    scanf("%d",&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        if(a[i]!=a[i-1])num[i]=1;
        else num[i]=num[i-1]+1;
    }
    prework();
    while(q--){
        int l,r;scanf("%d%d",&l,&r);
        printf("%d\n",query(l,r));
    }
    return 0;
}
int main(){
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        w33ha();
    }
    return 0;
}