POJ 3368-Frequent values（RMQ+离散化-最频繁的元素）

素颜马尾好姑娘i 2022-06-17 01:23 145阅读 0赞

Frequent values

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;18533</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;6692</td> 
  </tr> 
 </tbody> 
</table>

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

Source

[Ulm Local 2007][]

## 题目意思： ##

有N个升序排列好的元素，Q个查询，计算区间下标S~E之间出现最频繁的元素出现的次数。

## 解题思路： ##

分类在RMQ下面，有点懵，参考了大神的题解之后才明白……

首先用结构体保存元素值X，根据元素值的不同，将同一个值用一个POS下标记录：

\-1 -1 1 1 1 1 3 10 10 10 就被记录为 0 0 1 1 1 1 2 3 3 3

然后对元素进行离散化，用一个新的数组R记录每个元素当前出现的次数：

\-1 -1 1 1 1 1 3 10 10 10 就被记录为 1 2 1 2 3 4 1 1 2 3

对于查询区间S~E分三种情况讨论：

**①同一区间：**

POS相同即为同一区间，此时S~E区间内的元素个数e-s+1就是最大次数。

**②相邻区间：**

POS相差为1即为相邻区间，此时需要先找到两个区间的分隔点T(包含在前一区间内)，对第一个区间来说，区间内的元素个数T-S+1是最大次数；对第二个区间来说，最后一个元素出现的次数R\[e\]就是最大次数；对这两个值取MAX。

**③不相邻区间（用到RMQ）：**

与相邻区间相似，因为除了第一个区间以外，对于后面所有元素来说，使用RMQ处理R数组，则Maxmum(T+1,E)就是后面区间的最大次数；然后再按②的方法单独处理第一个区间求出最大次数T\-S+1，对这两个值取MAX。

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<map>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MAXN 100010
    int r[MAXN];//元素个数
    int dp[MAXN][20];
    int n,q;
    struct node
    {
        int x;//元素值
        int pos;//离散化之后的元素位置
    } a[MAXN];
    void rmq()
    {
        int temp=(int)(log((double)n)/log(2.0));
        for(int i=0; i<n; i++)
            dp[i][0]=r[i];
        for(int j=1; j<=temp; j++)
            for(int i=0; i<=n-(1<<j); i++)
                dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
    }
    
    int Maxmum(int s,int e)//计算s~e之间的最大元素
    {
        int k=(int)(log((double)e-s+1)/log(2.0));
        return max(dp[s][k],dp[e-(1<<k)+1][k]);
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        /*ios::sync_with_stdio(false);
        cin.tie(0);
        */
        while(cin>>n>>q)
        {
            if(n==0) break;
            memset(a,0,sizeof(a));
            memset(r,0,sizeof(r));
            memset(dp,0,sizeof(dp));
            scanf("%d",&a[0].x);
            r[0]=1;
            int cnt=0;//离散化的位置下标
            for(int i=1; i<n; ++i)//下标0-n-1
            {
                scanf("%d",&a[i].x);
                if(a[i].x==a[i-1].x)
                {
                    r[i]=r[i-1]+1;//统计当前位置上的数出现了多少次
                    a[i].pos=cnt;//离散化
                }
                else
                {
                    r[i]=1;
                    ++cnt;//位置下标更新
                    a[i].pos=cnt;
                }
            }
            rmq();//dp预处理
            for(int i=0; i<q; ++i)
            {
                int s,e;
                scanf("%d%d",&s,&e);
                --s,--e;
                if(a[s].pos==a[e].pos)  printf("%d\n",e-s+1);//同一区间
                else if(abs(a[s].pos-a[e].pos)==1)//相邻区间
                {
                    int t=s;
                    while(t<=e)//找到间隔点
                    {
                        if(a[t].pos!=a[t+1].pos) break;
                        ++t;
                    }
                    printf("%d\n",max((t-s+1),r[e]));
                }
                else if(abs(a[s].pos-a[e].pos)>1)//不相邻区间
                {
                    int t=s;
                    while(t<=e)//找到最前面的一个区间的间隔点
                    {
                        if(a[t].pos!=a[t+1].pos) break;
                        ++t;
                    }
                    printf("%d\n",max(t-s+1,Maxmum(t+1,e)));
                }
            }
        }
        return 0;
    }

[Ulm Local 2007]: http://poj.org/searchproblem?field=source&key=Ulm+Local+2007