一、題目描述
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
二、分析
一個可以用RMQ解決的問題，關鍵是如何轉化成RMQ問題，注意代碼的39行的處理，用ST算法，詳細算法：LCA問題（含RMQ的ST算法）。三、代碼
1
#include<iostream>
2#include<cmath>
3using namespace std;
4int n, q;
5int num;
6int m;
7int f[100001];
8int s[100001], t[100001];
9int mmax[18][100001];
10int pow2[18];
11void init_rmq()
12
{
13
memset(mmax, 0, sizeof(mmax));
14 for(int i=1; i<=m; i++)
15 mmax[0][i] = f[i];
16 int t1 = floor(log((double)m)/log(2.0));
17 for(int i=1; i<=t1; i++)
18 for(int j=1; j+pow2[i-1]<=n; j++)
19 mmax[i][j] = max(mmax[i-1][j], mmax[i-1][j+pow2[i-1]]);
20
}
21int find(int k)
22{
23 int i = 1, j = m;
24 while(i <= j)
25
{
26 int mid = (i+j) / 2;
27 if(s[mid] > k)
28 j = mid-1;
29 else if(t[mid] < k)
30 i = mid+1;
31 else
32 return mid;
33
}
34 return i;
35}
36int rmq(int i, int j)
37{
38 int a = find(i), b = find(j);
39 int aa = a+1, bb = b-1; //出現頻率只有在一頭一尾不與f中相同
40 int res = 1;
41 if(bb >= aa)
42 {
43 int k = floor(log((double)bb-aa+1) / log(2.0));
44 res = max(mmax[k][aa], mmax[k][bb - pow2[k] + 1]);
45 }
46 if(b > a)
47 {
48 res = max(res, t[a] - i + 1);
49 res = max(res, j - s[b] + 1);
50 }
51 else
52 res = max(res, j - i +1);
53 return res;
54}
55int main()
56{
57 while(1)
58 {
59 scanf("%d", &n);
60 if(n == 0)
61 break;
62 scanf("%d", &q);
63 scanf("%d", &num);
64 m = 0;
65 int last = num;
66 int counter = 1;
67 int head = 1;
68 memset(f, 0, sizeof(f));
69 memset(s, 0, sizeof(s));
70 memset(t, 0, sizeof(t));
71 for(int i=2; i<=n; i++)
72 {
73 scanf("%d", &num);
74 if(last == num)
75 counter++;
76 else
77 {
78 f[++m] = counter;
79 s[m] = head;
80 t[m] = i-1;
81 head = i;
82 last = num;
83 counter = 1;
84 }
85 }
86 f[++m] = counter;
87 s[m] = head;
88 t[m] = n;
89 n = m;
90 for(int i=0; i<18; i++)
91 pow2[i] = 1 << i;
92 init_rmq();
93 while(q--)
94 {
95 int i, j;
96 scanf("%d%d", &i, &j);
97 printf("%d\n", rmq(i, j));
98 }
99 }
100}
posted on 2009-07-01 16:24
Icyflame 閱讀(2351)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告