poj 3264 Frequent values - JAVA

Time Limit: 2000MS Memory Limit: 65536K

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

Source

Ulm Local 2007

/**** 
题目大意： 
    给出一串非降序列，然后询问某一段区间上连续相同的数字最长的长度是多少。 
    ~~~~线段树~~~~ 
****/  
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
typedef long long  ll;  
typedef unsigned long long ull;  
  
int dx[4]= {-1,1,0,0};  
int dy[4]= {0,0,-1,1}; //up down left right  
  
#define eps 1e-8  
#define inf 0x7fffffff  
#define debug puts("BUG")  
#define lson l,m,rt<<1  
#define rson m+1,r,rt<<1|1  
#define read freopen("in.txt","r",stdin)  
#define write freopen("in.txt","w",stdout)  
#define Mem(a,x) memset(a,x,sizeof(a))  
#define maxn 100010  
  
/**** 
 **思路： 
        我们不用所给的区间建立线段树，那样会增加线段树的复杂程度（会有很多的变量）。 
        我们用出现的数字的频数来建立线段树，因为是非降序列，因此，只要对于相同的数字只存一次， 
        没有任何两个数字是相同的。 
        并且，原串可以变为：第一个数字有x1个，第二个数字有x2个。。。。第num个数字有xnum个。 
 
        我们以得到的新串建立线段树，线段树维护的值为某一段区间的最大值。此时线段树的区间值的意义 
        变成了第l个数和第r个数。 
 
        我们需要对原来的区间信息进行储存，需要将原来每一个数字的开始位置存起来，以便对查询的区间端点进行转换， 
        换成线段树的区间值。在输入的时候，我们不仅可以得到新串，还可以得到区间端点信息，一起处理即可。 
 
        查询时，我们需要对查询的区间值进行转换，将其转换为：位置l位于第l0个数字之间，位置r位于第r0个数字之间， 
        这需要使用二分查找，如果不用的话，线段树就相当于白写了，没试过= =！ 
 
        要注意的是，查询时的l和r所处的位置，会使第l0个数的连续截断，r也是如此。因此，需要将这两部分截断的内容拿出来， 
        然后查询l0+1到r0-1这个范围的最大值，这样，答案就是三个数当中的最大值。但有可能会出现该区间是由两部分截断的内容组成的， 
        此时，线段树的查询就没有意义了，可以先判断，也可以稍微处理一下线段树。 
****/  
int  len[maxn<<2];//第i个数字连续的长度  
int  Max[maxn<<2];//线段树，存从第l个数字到第r个数字中，数字连续最长的长度  
int   ls[maxn<<2];//第i个数字的起始位置  
int num,x;        //num是有多少个不同的数字，x是用于线段树初始化的计数器  
  
void init()  
{//初始化  
    num=1;  
    x=1;  
    Mem( len,0);  
    Mem( Max,0);  
    Mem(  ls,0);  
}  
  
void PushUp(int rt)  
{//线段树更新  
    Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);  
}  
  
void build(int l,int r,int rt)  
{//建立线段树  
    if(l==r)  
    {  
        Max[rt]=len[x++];  
        return ;  
    }  
    int m=(l+r)>




>1;  
    build(lson);  
    build(rson);  
    PushUp(rt);  
}  
  
int query(int L,int R,int l,int r,int rt)  
{//查询  
    if(L>R)//这种情况是可能出现的  
        return 0;  
    if(L<=l&&r<=R)  
        return Max[rt];  
    int m=(l+r)>>1;  
    int ans=0;  
    if(L<=m)  
        ans=max(ans,query(L,R,lson));  
    if(R>m)  
        ans=max(ans,query(L,R,rson));  
    return ans;  
}  
  
int bisect(int k)//二分查找  
{  
    if(k>=ls[num])//最后一个数字需要特判  
        return num;  
    int l=1,r=num;  
    while(l<=r)  
    {  
        int m=(l+r)>>1;  
        if(k>=ls[m]&&kls[m]&&k>ls[m+1])  
            l=m+1;  
        else if(k>ls[m]&&k==ls[m+1])//找到的条件  
            return m+1;  
        else  
            r=m;  
    }  
}  
  
int main()  
{  
    //read;  
    int n,m;  
    while(~scanf("%d",&n)&&n)  
    {  
        init();  
        scanf("%d",&m);  
        int x0;    scanf("%d",&x0);//输入  
        ls[num]=1; len[num]=1;  
        for(int i=2;i<=n;i++)  
        {  
            int x1;  
            scanf("%d",&x1);  
            if(x1!=x0)//判断是否连续出现  
            {  
                num++;ls[num]=i;//储存位置  
            }  
            len[num]++;//更新长度  
            x0=x1;//为下一个值做铺垫  
        }  
        ls[num+1]=n+1;//这个没用  
        build(1,num,1);//建树  
        for(int i=1;i<=m;i++)  
        {  
            int l,r,l0,r0;  
            int Max1=0,Max2=0,Max3=0,ans=0;  
            scanf("%d%d",&l,&r);  
            l0=bisect(l),r0=bisect(r);//二分求位置  
            Max1=ls[l0+1]-l,Max2=r-ls[r0]+1;//求两段截断部分的长度  
            if(l0==r0)//这种情况，就不需要继续算了  
            {  
                printf("%d\n",r-l+1);  
                continue;  
            }  
            else if(r0==l0+1)//这种也是  
            {  
                ans=max(Max1,Max2);  
                printf("%d\n",ans);  
                continue;  
            }  
            Max3=query(l0+1,r0-1,1,num,1);//完整区间中的最大值  
            ans=max(Max3,Max2),ans=max(Max1,ans);  
            printf("%d\n",ans);  
        }  
    }  
    return 0;  
}