HDU1806 Frequent values - c++编程基础

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
现将其离散化，那么就转化成连续区间最值，可用RMQ解决。
    #include 
   
    
    #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; const int maxn = 100000+10; vector
          
            val,cnt; int res[maxn][20]; int num[maxn],lft[maxn],rgt[maxn]; int n,q; void init_RMQ(){ int nt = cnt.size(); for(int i = 0; i < nt; i++) res[i][0] = cnt[i]; for(int j = 1; (1<
           
            > n &&n){ cin >> q; val.clear(); cnt.clear(); scanf("%d",&now); cnt.push_back(1); for(int i = 1; i < n; i++){ int t; scanf("%d",&t); if(t==now) cnt[cnt.size()-1]++; else{ now = t; cnt.push_back(1); } } init_RMQ(); int cur = 0; for(int i = 0; i < cnt.size(); i++){ int tl = cur,tr = cur+cnt[i]-1; for(int j = 0; j < cnt[i]; j++){ num[cur] = i; lft[cur] = tl; rgt[cur++] = tr; } } while(q--){ int L,R; scanf("%d%d",&L,&R); if(L > R) swap(L,R); L--;R--; int sta = num[L],ed = num[R]; if(sta==ed){ printf("%d\n",R-L+1); continue; } int ans = max(rgt[L]-L+1,R-lft[R]+1); sta++; ed--; if(sta<=ed) ans = max(ans,RMQ(sta,ed)); printf("%d\n",ans); } } return 0; }