Frequent values

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1476 Accepted Submission(s): 541

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 a₁ , ... , a_n(-100000 ≤ a_i ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: a_i ≤ a_i+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

上一题的弱化版 http://www.cnblogs.com/liyinggang/p/5351694.html

有个RMQ的解法，利用游标编码，代码简单，但是理解可能复杂点

#include<iostream>

#include<cstdio>

#include<algorithm>

#define N 100005

using namespace std;

int a[N];

struct Tree{

    int l,r;

    int lv,rv,mv;

}tree[*N];

void PushUp(int l,int r,int idx){

    tree[idx].lv = tree[idx<<].lv;

    tree[idx].rv = tree[idx<<|].rv;

    tree[idx].mv = max(tree[idx<<].mv,tree[idx<<|].mv);

    int mid = (l+r)>>;

    int len = r- l+;

    if(a[mid]==a[mid+]){

        if(tree[idx].lv==len-(len>>)) tree[idx].lv+=tree[idx<<|].lv;

        if(tree[idx].rv==(len>>)) tree[idx].rv+=tree[idx<<].rv;

        tree[idx].mv = max(tree[idx].mv,tree[idx<<].rv+tree[idx<<|].lv);

    }

}

void build(int l,int r,int idx){

    tree[idx].l = l;

    tree[idx].r = r;

    if(l==r){

        tree[idx].lv = tree[idx].rv = tree[idx].mv = ;

        return;

    }

    int mid = (l+r)>>;

    build(l,mid,idx<<);

    build(mid+,r,idx<<|);

    PushUp(l,r,idx);

}

int query(int l,int r,int idx){

    if(tree[idx].l>=l&&tree[idx].r<=r){

        return tree[idx].mv;

    }

    int mid = (tree[idx].l+tree[idx].r)>>;

    int ans = ;

    if(l<=mid) ans = max(ans,query(l,r,idx<<));

    if(r>mid) ans=max(ans,query(l,r,idx<<|));

    if(a[mid]==a[mid+]){

        ans = max(ans,min(mid-l+,tree[idx<<].rv)+min(r-mid,tree[idx<<|].lv));

    }

    return ans;

}

int main()

{

    int n,m;

    while(scanf("%d",&n)!=EOF,n){

        scanf("%d",&m);

        for(int i=;i<=n;i++){

            scanf("%d",&a[i]);

        }

        build(,n,);

        while(m--){

            int a,b;

            scanf("%d%d",&a,&b);

            printf("%d\n",query(a,b,));

        }

    }

    return ;

}

巴特西

hdu 1806(线段树区间合并)

Frequent values

最新文章

热门文章