UVa11235 FrequentValues（RMQ）

时间：2023-03-08 16:42:13
UVa11235 FrequentValues（RMQ）

Problem F: Frequent values

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 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 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 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 10

2 3

1 10

5 10

0

Sample Output

1

4

3

题目大意：
给一个非降序排列的整数数组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）

详见代码：
 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define inf -0x3f3f3f3f

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 int num[MAXN], coun[MAXN], Left[MAXN], Right[MAXN];

 int n, q, a, last, tot;

 int DP[MAXN][];

 void init_RMQ()

 {

     mem0(DP);

     for(int i=;i<=tot;i++) DP[i][] = coun[i];

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

     {

         for(int i=;i+(<<j)<=tot;i++)

         {

             DP[i][j] = max(DP[i][j-], DP[i+(<<(j-))][j-]);

         }

     }

 }

 int RMQ(int L, int R)

 {

     if(L > R) return ;

     int k = ;

     while((<<(+k)) <= R-L+) k++;

     return max(DP[L][k], DP[R-(<<k)+][k]);

 }

 int main()

 {

 //    FOPENIN("in.txt");

 //    FOPENOUT("out.txt");

     while(~scanf("%d", &n) && n)

     {

         scanf("%d", &q);

         tot = ; mem0(Left); mem0(Right); mem0(coun);

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

         {

             scanf("%d", &a);

             if(i==) { ++tot;   last=a;  Left[tot] = ; }

             if(last == a) { num[i]=tot; coun[tot]++; Right[tot]++; }

             else { num[i]=++tot; coun[tot]++; Left[tot]=Right[tot]=i; last=a; }

         }

         init_RMQ();

         int l, r;

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

         {

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

             if(num[l] == num[r]) { printf("%d\n", r-l+);  continue; }

             printf("%d\n", max( RMQ(num[l]+, num[r]-), max( Right[num[l]]-l+, r-Left[num[r]]+ ) ) );

         }

     }

     return ;

 }

相关文章