Frequent values

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1459 Accepted Submission(s): 535

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 
Hint
 A naive algorithm may not run in time! 

题意：

查找区间中出现频率最高的，并输出出现次数。

思路：

开始想了很久不知道怎么用到RMQ的，总感觉和最值没什么关系，后来发现对连续的数编号然后求出最大值就好了。

只是需要判断一下不是从1开始的，所以用的二分查找。

但是强行被二分Gank一波。总感觉二分用的不怎么熟练，好久去研究一下。就因为设置的方向不一样，写起来特别麻烦，导致后来还是要重写。

假设我想取一个最接近左边的值，所以设定的l = mid，但是就会导致2和3的时候卡死。后来换了下方向就行了

当你取到3的时候，下一次还是会往下跳，- -！基础真的糟

 /**/#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             using namespace std;typedef long long ll;typedef long double ld;using namespace std;const int maxn = 100010;int dp[maxn][20];int m[maxn];int a[maxn];int b[maxn];void iniRMQ(int n,int c[]){ m[0] = -1; for(int i = 1; i <= n; i++) { m[i] = ((i&(i-1)) == 0)? m[i-1]+1:m[i-1]; dp[i][0] = c[i]; } for(int j = 1; j <= m[n]; j++) { for(int i = 1; i+(1<
              
               <= n; i++) dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); }}int RMQ(int x,int y){ int k = m[y-x+1]; return max(dp[x][k],dp[y-(1<
               
                >1); if(a[mid] >= to) r = mid; else l = mid+1; } return r;}int main(){ int n,m,T; while(scanf("%d",&n) != EOF && n) { scanf("%d",&m); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); } int t; for(int i = n; i >= 1; i--) { if(i == n) t = 1; else { if(a[i] == a[i+1])t++; else t=1; } b[i] = t; }// for(int i = 1;i <= n;i++)// printf("%d ",b[i]); iniRMQ(n,b); while(m--) { int s,t,ans; scanf("%d%d",&s,&t); int tl = get_bi(s,t);// printf("%d\n",tl); ans = t- tl+1; if(tl-1 > s) ans = max(ans,RMQ(s,tl-1)); printf("%d\n",ans); } } return 0;}

转载于:https://www.cnblogs.com/Przz/p/5409635.html

你可能感兴趣的文章