UVA - 11235
题目大意：
给一个非降序排列的整数数组a，你的任务是对于一系列询问(i, j)，回答ai,ai+1…aj中次数出现最多的值所出现的次数。
这是一个 RMQ 问题，蓝书198页有讲解
ST(Sparse-Table) 算法中：
令 dp(i, j) 表示从i开始的，长度为 $2^j$ 的一段元素的最值，则可以用递推的方法计算 dp(i, j)：
递推方程：$dp(i, j) = min/max{ dp(i, j-1), dp(i+2^{j-1}, j-1) }$
分析：
由于数列是非降序的，所以所有相等的数都会聚集在一起。这样我们就可以把整个数组进行游程编码 (Run Length Encoding, RLE)。如-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段的左边界和右边界，用cnt[i]表示第i段有cnt[i]个相同的数。 这样的话每次查询 (L, R) 就只要计算 (Right[L]-L+1), (R-Left[R]+1) 和 RMQ(num[L]+1, num[R]-1) 这三个值的最大值就可以了。
其中，RMQ 是对 cnt 数组进行区间查询的结果。
特殊的，如果 L 和 R 在同一个区间内的话，那么结果就是（R-L+1）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=1e5+10;
int cnt[MAXN];
int num[MAXN],Left[MAXN],Right[MAXN];
int dp[MAXN][16+5];
int n,q,a,total,last;
void RMQ_init(){
memset(dp,0,sizeof dp);
for(int i=1;i<=total;i++) dp[i][0]=cnt[i];
for(int j=1;(1<<j)<=total;j++){
for(int i=1;i+(1<<j)<=total;i++){
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
}
int RMQ(int L,int R){
if(L>R) return 0;
int k=0;
while((1<<(1+k))<=R-L+1) k++;
return max(dp[L][k],dp[R-(1<<k)+1][k]);
}
int main(){
while(~scanf("%d",&n)&&n){
scanf("%d",&q);
memset(cnt,0,sizeof cnt);
memset(Right,0,sizeof Right);
memset(Left,0,sizeof Left);
total=0;
for(int i=1;i<=n;i++){
scanf("%d",&a);
if(i==1){
++total;
last=a;
Left[total]=1;
}
if(a==last){
cnt[total]++;
num[i]=total;
Right[total]++;
}else{
last=a;
num[i]=++total;
Left[total]=Right[total]=i;
cnt[total]++;
}
}
RMQ_init();
int L,R;
while(q--){
scanf("%d%d",&L,&R);
if(num[L]==num[R]) printf("%d\n",R-L+1);
else printf("%d\n",max(RMQ(num[L]+1,num[R]-1),max(Right[num[L]]-L+1,R-Left[num[R]]+1)));
}
}
return 0;
}
|