poj 3368 Frequent values（RMQ）

题意：给定n个数，顺序为非下降，询问某个区间内的数出现最多的数的出现次数。。

大白书上的例题。。算是RMQ变形了，

对原数组重新分段，并标记相同的个数为该段的数值，然后RMQ...

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 100005;
 8 const int maxm = 30;
 9 
10 int d_max[maxn][maxm],a[maxn];
11 int n,t;
12 int val[maxn],cnt[maxn],num[maxn],l[maxn],r[maxn];
13 
14 void RMQ_init()
15 {
16     int i,j;
17     memset(d_max,0,sizeof(d_max));
18     for(i = 0; i <= t; i++)
19     {
20         d_max[i][0] = cnt[i];
21     }
22     for(j = 1; (1<<j) <= t; j++)
23     for(i = 1; i + j - 1 <= t; i++)
24     {
25         d_max[i][j] = max(d_max[i][j-1], d_max[i + (1<<(j-1))][j-1]);
26     }
27 }
28 
29 int RMQ_max(int l, int r)
30 {
31     if(l>r)
32     return 0;
33 
34     int k = 0;
35     while((1<<(k+1)) <= r-l+1)
36     k++;
37     return max(d_max[l][k], d_max[r-(1<<k)+1][k]);
38 }
39 int main()
40 {
41     int i, j, le, rig;
42     int q, ans, k, maxs;
43     while(~scanf("%d",&n) && n)
44     {
45         scanf("%d",&q);
46         for(i = 1; i <= n; i++)
47         {
48             scanf("%d",&a[i]);
49         }
50         i = 1;
51         t = 1;
52         while(i <= n)
53         {
54             j = i;
55             ans = 0;
56             while(a[j] == a[i] && j <=n)
57             {
58                 j++;
59                 ans++;
60             }
61             for(k = i; k < j; k++)
62             {
63                 num[k] = t; //位置k的编号
64                 l[k] = i;  //位置k的最左端编号
65                 r[k] = j-1; //位置k的最右端编号
66             }
67             val[t] = a[i]; //第i段的数值
68             cnt[t] = ans;  //第i段的出现次数
69             t++; i = j;
70         }
71         RMQ_init();
72         while(q--)
73         {
74             scanf("%d%d",&le, &rig);
75             if(num[le] == num[rig])
76             maxs = rig - le +1;
77             else
78             {
79                 maxs = max(r[le] - le + 1, rig - l[rig] + 1);
80                 maxs = max(maxs, RMQ_max(num[le]+1, num[rig]-1));
81             }
82             printf("%d\n",maxs);
83         }
84     }
85     return 0;
86 }

poj 3368 Frequent values（RMQ）

推荐阅读