Problem F: Frequent values

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 Specification

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 Specification

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 102 31 105 100

Sample Output

143 题目大意： 给一个非降序排列的整数数组a，你的任务是对于一系列询问(i, j)，回答ai,ai+1...aj中次数出现最多的值所出现的次数。 分析： 由于数列是非降序的，所以所有相等的数都会聚集在一起。这样我们就可以把整个数组进行编码。如-1,1,1,2,2,2,4就可以编码成(-1,1),(1,2),(2,3),(4,1)表示（a，b）数组中的a连续出现了b次。用num[i]表示原数组下表是i的数在编码后的第num[i]段。left[i],right[i]表示第i段的左边界和右边界，用coun[i]表示第i段有conu[i]个相同的数。这样的话每次查询(L, R)就只要计算(right[L]-L+1),(R-left[R]+1)和RMQ(num[L]+1, num[R]-1)这三个值的最大值就可以了。 其中，RMQ是对coun数组进行取件查询的结果。 特殊的，如果L和R在同一个区间内的话，那么结果就是（R-L+1） 详见代码：

1 #include  2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 using namespace std;15 #define INF 0x3f3f3f3f16 #define inf -0x3f3f3f3f17 #define lson k<<1, L, mid18 #define rson k<<1|1, mid+1, R19 #define mem0(a) memset(a,0,sizeof(a))20 #define mem1(a) memset(a,-1,sizeof(a))21 #define mem(a, b) memset(a, b, sizeof(a))22 #define FOPENIN(IN) freopen(IN, "r", stdin)23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)24 25 template
                  
                    T CMP_MIN(T a, T b) { return a < b; }26 template
                   
                     T CMP_MAX(T a, T b) { return a > b; }27 template
                    
                      T MAX(T a, T b) { return a > b ? a : b; }28 template
                     
                       T MIN(T a, T b) { return a < b ? a : b; }29 template
                      
                        T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }30 template
                       
                         T LCM(T a, T b) { return a / GCD(a,b) * b; }31 32 //typedef __int64 LL;33 typedef long long LL;34 const int MAXN = 100005;35 const int MAXM = 100005;36 const double eps = 1e-12;37 38 int num[MAXN], coun[MAXN], Left[MAXN], Right[MAXN];39 int n, q, a, last, tot;40 int DP[MAXN][20];41 42 void init_RMQ()43 {44 mem0(DP);45 for(int i=1;i<=tot;i++) DP[i][0] = coun[i];46 for(int j=1;(1<
                        
                         <=n;j++)47 {48 for(int i=1;i+(1<
                         
                          <=tot;i++)49 {50 DP[i][j] = max(DP[i][j-1], DP[i+(1<<(j-1))][j-1]);51 }52 }53 }54 55 int RMQ(int L, int R)56 {57 if(L > R) return 0;58 int k = 0;59 while((1<<(1+k)) <= R-L+1) k++;60 return max(DP[L][k], DP[R-(1<

转载于:https://www.cnblogs.com/gj-Acit/p/3584686.html

你可能感兴趣的文章