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; }
|