POJ 3368 Frequent values RMQ ST算法/线段树

Frequent values

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 15229		Accepted: 5550

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

Source

题意：

给你一个非递减序列。有m次询问，每次询问区间之间出现最多的数字出现的次数。

题解：

RMQ/线段树

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

using namespace std ;

typedef long long ll;

#define inf 100000

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//******************************************************************

struct ss{

int l,r,num,v;

}a[];

int counts[];

int dp[][],n,m,p;

void rmq_init()

{

   memset(dp,,sizeof(dp));

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

    dp[i][]=counts[i];

   }

   int k=floor(log((double)n+)/log(2.0));

   for(int j=;j<=k;j++)

   {

       for(int i=;i+(<<j)-<=p;i++)

       {

          int oo=i+(<<(j-));

          dp[i][j]=max(dp[i][j-],dp[oo][j-]);

       }

   }

}

int RMQ(int x,int y)

{

    int oo=floor(log((double)y-x+)/log(2.0));

    return max(dp[x][oo],dp[y-(<<(oo))+][oo]);

}

void work()

{

    int l,r;

    for(int i=;i<=m;i++)

    {

        scanf("%d%d",&l,&r);

        if(a[l].num==a[r].num){

            cout<<r-l+<<endl;

        }

        else {

            int ans=a[l].r-l+;

            ans=max(r-a[r].l+,ans);

            l=a[l].num+;

            r=a[r].num-;

           if(l<=r) ans=max(ans,RMQ(l,r));

            cout<<ans<<endl;

        }

    }

}

void init()

{

    int f=,r=,l=;

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

    {

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

        if(f&&a[i].v!=a[i-].v)

        {

            counts[p]=r-l+;

            for(int j=l;j<=r;j++)

                a[j].num=p,a[j].l=l,a[j].r=r;

            r++;

            p++;

            l=r;

        }

        else if(f){

            r++;

        }

        if(f==)

        {

            l=;

            r=,f=;

            p=;

        }

    }

    counts[p]=r-l+;

    for(int j=l;j<=r;j++)

                a[j].num=p,a[j].l=l,a[j].r=r;

   // for(int i=1;i<=n;i++)cout<<counts[i]<<" ";

}

int main()

{

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

    {

        if(n==)break;

        init();

        rmq_init();

        work();

    }

    return ;

}

RMQ

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

using namespace std ;

typedef long long ll;

#define inf 100000

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//******************************************************************

struct ss

{

    int l,r,v,num;

}tr[*],a[];

int counts[];

int n,m,p;

void build(int k,int s,int t)

{

    tr[k].l=s;

    tr[k].r=t;

    if(s==t){

        tr[k].v=counts[s];

        return ;

    }

    int mid=(s+t)>>;

    build(k<<,s,mid);

    build(k<<|,mid+,t);

    tr[k].v=max(tr[k<<].v,tr[k<<|].v);

}

int ask(int k,int s,int t)

{

    if(s==tr[k].l&&t==tr[k].r)

    {

        return tr[k].v;

    }

    int mid=(tr[k].l+tr[k].r)>>;

    if(t<=mid)return ask(k<<,s,t);

    else if(s>mid)return ask(k<<|,s,t);

    else {

        return max(ask(k<<,s,mid),ask(k<<|,mid+,t));

    }

}

void init()

{

    int f=,l=,r=;

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

    {

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

        if(f&&a[i].v!=a[i-].v)

        {

            counts[p]=r-l+;

            for(int j=l;j<=r;j++)a[j].l=l,a[j].r=r,a[j].num=p;

            r++;

            l=r;

            p++;

        }

        else if(f){

            r++;

        }

        if(!f)

        {

            f=l=;

            r=p=;

        }

    }

    counts[p]=r-l+;

   for(int j=l;j<=r;j++)a[j].l=l,a[j].r=r,a[j].num=p;

   ///for(int i=1;i<=p;i++)cout<<counts[i]<<" ";

}

int main()

{

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

    {

        p=;

        if(n==)break;

        init();

        build(,,p);

        // cout<<p<<endl;

           int x,y;

        for(int i=;i<=m;i++)

        {

            scanf("%d%d",&x,&y);

            if(a[x].num==a[y].num){

                cout<<y-x+<<endl;

            }

            else {

                int ans=a[x].r-x+;

                ans=max(ans,y-a[y].l+);

                x=a[x].num+;

                y=a[y].num-;

                if(x<=y)ans=max(ask(,x,y),ans);

                cout<<ans<<endl;

            }

        }

    }

    return ;

}

线段树

巴特西

POJ 3368 Frequent values RMQ ST算法/线段树

最新文章

热门文章