首页 > 代码库 > poj 3368 Frequent values（线段树）

poj 3368 Frequent values（线段树）

2024-07-27 21:16:38   221人阅读

Frequent values
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 13516 Accepted: 4971

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


因为是非递减数列，相同的元素必须是连在一块的，可以统计不同元素的个数，以元素的个数建树，给出一段区间，再二分查找出现在第几个元素，特殊考虑最前和最后，中间的用线段树。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=100000+100;
int p;
int tree[maxn<<2];
int num[maxn],sum[maxn];
int a[maxn];
void build(int rt,int l,int r)
{
    if(l==r)
    {
     tree[rt]=num[l];
     return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
int query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&R>=r)
    {
    return tree[rt];
    }
    int ans=0;
    int mid=(l+r)>>1;
    if(L<=mid)
    ans=query(rt<<1,l,mid,L,R);
    if(R>mid)
    ans=max(ans,query(rt<<1|1,mid+1,r,L,R));
    return ans;
}

int find(int k)
{
    int l=1,r=p;
    int m;
    while (l<=r)
    {
        m=(l+r)>>1;
        if(k>sum[m])
            l=m+1;
        else if(k<sum[m])
            r=m-1;
        else
            break;
    }
    if(sum[m-1]>=k)
        return m-1;
    else if(sum[m]>=k)
        return m;
    else
        return m+1;
}
int main()
{
    int n,m;
    while(~scanf("%d",&n)&&n)
    {
        memset(num,0,sizeof(num));
        memset(sum,0,sizeof(sum));
        memset(tree,0,sizeof(tree));
        scanf("%d",&m);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        int temp;
        temp=0;
         p=1;
        num[p]=1;
        sum[0]=0;
        for(int i=1;i<n;i++)
        {
            if(a[temp]==a[i])
            {
                num[p]++;
            }
            else
            {
                temp=i;
                sum[p]=sum[p-1]+num[p];
                p++;
                num[p]=1;
            }
        }
        sum[p]=sum[p-1]+num[p];
        build(1,1,p);
        int l,r;
        for(int i=0;i<m;i++)
        {
            int u,v;
            int ans=0;
            scanf("%d%d",&l,&r);
            u=find(l);
            v=find(r);
            ans=sum[u]-l+1;
            if(u==v)
            {
                printf("%d\n",r-l+1);
                continue;
            }
            if(u+1<=v-1)
            ans=max(ans,query(1,1,p,u+1,v-1));
            ans=max(ans,r-sum[v-1]);
            printf("%d\n",ans);
        }
    }
}



poj 3368 Frequent values（线段树）


联系
我们