UVa 11235 频繁出现的数值

题意：

给出一个非降序排列的整数数组a1，a2，...，an，你的任务是对于一系列询问（i，j），回答ai，ai+1，...aj中出现次数最多的值所出现的次数。

思路：

首先对整个数组进行游程编码，比如（-1,1,1,2,2,2,4）就可以编码成（-1,1），（1,2），（2,3），（4,1），其中（a，b）表示有b个连续的a。

用count[i]表示第i段的出现次数，num[p]表示第p个数所在的段，left[i],right[i]表示第i段的左右坐标值。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 100000 + 5;
 7 
 8 int n, q, ret;
 9 int a[maxn];
10 int count[maxn];
11 int num[maxn];
12 int left[maxn];
13 int right[maxn];
14 int d[maxn][20];
15 
16 void RMQ_init()
17 {
18     for (int i = 1; i <= ret; i++)
19         d[i][0] = ::count[i];
20     for (int j = 1; (1 << j) <= ret;j++)
21     for (int i = 1; i + (1 << j) <= ret; i++)
22         d[i][j] = max(d[i][j - 1], d[i + (1 << (j-1))][j - 1]);
23 }
24 
25 int RMQ(int L, int R)
26 {
27     int k = 0;
28     while ((1 << (k + 1)) <= R - L + 1)  k++;
29     return max(d[L][k], d[R - (1 << k) + 1][k]);
30 }
31 
32 int main()
33 {
34     //freopen("D:\txt.txt", "r", stdin);
35     while (cin >> n && n)
36     {
37         cin >> q;
38         for (int i = 1; i <= n; i++)
39             cin >> a[i];
40         ret = 1;
41         for (int i = 1; i <= n; i++)
42         {
43             num[i] = ret;
44             ::left[ret] = i;
45             int cnt = 1;
46             while (a[i] == a[i + 1])
47             {
48                 num[i + 1] = ret;
49                 cnt++;
50                 i++;
51             }
52             ::right[ret] = i;
53             ::count[ret] = cnt;
54             ret++;
55         }
56         RMQ_init();
57         int L, R;
58         int ans;
59         for (int i = 0; i < q; i++)
60         {
61             cin >> L >> R;
62             int k1 = num[L];
63             int k2 = num[R];
64             ans = 0;
65             if (k1 == k2)  cout << R - L + 1 << endl;
66             else if (k2 - k1 == 1)
67             {
68                 ans = max(::right[k1] - L + 1, R - ::left[k2] + 1);
69                 cout << ans << endl;
70             }
71             else
72             {
73                 ans = max(::right[k1] - L + 1, R - ::left[k2] + 1);
74                 ans = max(ans, RMQ(k1+1, k2-1));
75                 cout << ans << endl;
76             }
77         }
78     }
79 }