uva11235 frequent values（Sparse Table）

题目链接：https://vjudge.net/problem/UVA-11235

题意：

给一个非降序的整数数组a，求[i, j]中出现最多次数的数，出现了几次。

思路：

明显的是RMQ问题。白书上用的是Sparse Table，这个叫ST表就变成了表表….

一开始思路就被定死，求出现最多的数出现的次数，感觉无从下手。看到刘汝佳的做法，还有这种操作….先进行游程编码，把相同的数压缩成一个点，对于所求的区间[i, j]，那么i和j所对应的a[i]和a[j]必然属于某个对应的压缩后的点，对这些压缩后的点建树就可以了，维护最大值。

先判断i和j对应的区间是否相同，相同的话，答案就是j-i+1 否则为max( right[idx[i]] - i +1, j - left[idx[j]] +1, RMQ(idx[i]+1, idx[j]-1) ) idx[i]表示i所在的区间号，left为该区间的开始位置，right为该区间的结束位置。

竟然1A…

#include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; const int maxn = 1e6 + 1000; int x, y, tmp; int num[maxn], lf[maxn], rg[maxn], val[maxn], cnt[maxn]; class SparseTable{ public: int **d, n, m; SparseTable(){} ~SparseTable(){ for(int i=0; i<n; ++i) delete []d[i]; delete []d; } int cal_len(int n){ return (int)(log(n*1.0)/log(2.0)); } void init(int A[], int n){ this->n = n; m = cal_len(n) + 200; d = new int*[n]; for(int i=0; i<n; ++i) d[i] = new int[m]; for(int i=0; i<n; ++i) d[i][0] = A[i]; for(int j=1; (1<<j)<=n; ++j){ for(int i=0; i+(1<<j)-1<n; ++i){ d[i][j] = max(d[i][j-1], d[i+(1<<(j-1))][j-1]); // minimal or maximal } } } int RMQ(int L, int R){ int k = 0; while((1<<(k+1)) <= R-L+1) ++k; return max(d[L][k], d[R-(1<<k)+1][k]); // minimal or maximal } }; int main(){ int n, q; ios::sync_with_stdio(false); while(cin>>n){ if(n==0) break; cin>>q; int pre=-maxn, tot=-1; memset(num, 0, sizeof(num)); memset(lf, 0, sizeof(lf)); memset(rg, -1, sizeof(rg)); memset(val, 0, sizeof(val)); memset(cnt, 0, sizeof(cnt)); for(int i=0; i<n; ++i){ cin>>tmp; if(tmp!=pre){ ++tot; val[tot] = tmp; cnt[tot]++; if(i-1>=0) rg[i-1] = i-1; lf[i] = i; pre = tmp; } else{ cnt[tot]++; lf[i] = lf[i-1]; } num[i] = tot; } rg[n-1] = n-1; for(int i=n-2; i>=0; --i){ if(rg[i]==-1) rg[i] = rg[i+1]; } SparseTable ST; ST.init(cnt, tot+1); for(int i=0; i<q; ++i){ cin>>x>>y; --x; --y; int no1 = num[x]; int no2 = num[y]; if(no1==no2){ cout<<y-x+1<<endl; } else{ int ans1 = rg[x] - x + 1; int ans2 = y - lf[y] + 1; int ans3; if(num[x]+1>num[y]-1){ ans3 = 0; } else{ ans3 = ST.RMQ(num[x]+1, num[y]-1); } cout<<max(max(ans1, ans2), ans3)<<endl; } } } return 0; }