首页 > > 程序设计 > C/C++ >

hdu 1806 Frequent values

2018-06-17 21:46:26来源：未知阅读 ()

Frequent values

Time Limit : 4000/2000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 25 Accepted Submission(s) : 11

Problem Description

You are given a sequence of n integers a₁ , a₂ , ... , a_n 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 a_i , ... , a_j.

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

PKU

区间求最大值，插入点易错点很多。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
int a[100010];
int ans;
struct node
{
    int l,r;
    int lcnt,ln,rcnt,rn;
    int cnt,num;
}t[100010<<2];
void build(int l,int r,int n)
{
    t[n].l=l;
    t[n].r=r;
    if(l==r)
    {
        t[n].cnt=t[n].lcnt=t[n].rcnt=1;
        t[n].num=t[n].ln=t[n].rn=a[l];
        return;
    }
    int m=(l+r)>>1;
    build(l,m,n<<1);
    build(m+1,r,n<<1|1);
    if(t[n<<1].cnt>=t[n<<1|1].cnt){
        t[n].cnt=t[n<<1].cnt;
        t[n].num=t[n<<1].num;
    }
    else{
        t[n].cnt=t[n<<1|1].cnt;
        t[n].num=t[n<<1|1].num;
    }
    t[n].lcnt=t[n<<1].lcnt;
    t[n].rcnt=t[n<<1|1].rcnt;
    t[n].ln=t[n<<1].ln;
    t[n].rn=t[n<<1|1].rn;
    if(t[n<<1].rn==t[n<<1|1].ln)
    {
        if(t[n<<1].rcnt+t[n<<1|1].lcnt>t[n].cnt)
        {
            t[n].cnt=t[n<<1].rcnt+t[n<<1|1].lcnt;
            t[n].num=t[n<<1|1].ln;
        }

        if(t[n<<1].rn==t[n<<1|1].rn){
            t[n].rcnt+=t[n<<1].rcnt;
        }
        if(t[n<<1|1].ln==t[n<<1].ln){
            t[n].lcnt+=t[n<<1|1].lcnt;
        }

    }
}
void query(int l,int r,int n)
{
    if(t[n].l==l&&t[n].r==r){
        ans=max(t[n].cnt,ans);
        return;

    }
    if(l>=t[n<<1|1].l){
        query(l,r,n<<1|1);
    }
    else if(r<=t[n<<1].r){
        query(l,r,n<<1);
    }
    else{
        query(l,t[n<<1].r,n<<1);
        query(t[n<<1|1].l,r,n<<1|1);
        if(t[n<<1].rn == t[n<<1|1].ln)
        {
            int ans1=0,ans2=0;
            if(a[l]!=t[n<<1].rn)
                ans1=t[n<<1].rcnt;
            else ans1=t[n<<1].r-l+1;
            if(a[r]!=t[n<<1|1].ln)
                ans2=t[n<<1|1].lcnt;
            else ans2=r-t[n<<1].r;
            ans=max(ans,ans1+ans2);
            return ;
        }
    }


}
int main()
{
    int n,q;
    while(scanf("%d",&n),n)
    {
        scanf("%d",&q);
        for(int i =1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        build(1,n,1);
        for(int i = 0;i<q;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==y){
                puts("1");
                continue;
            }
            ans=0;
            query(x,y,1);
            cout<<ans<<endl;
        }
    }
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有