poj 3368 Frequent values（段树）

Frequent values

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

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

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

代码：

#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（段树）

最新文章

热门文章