POJ 3368 Frequent values——RMQ

POJ 3368 Frequent values——RMQ

题意：

求区间最大频数

思路：

半暴力扫描+RMQ

#include #include #include #include #include using namespace std;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;int n, q, v[maxn], a[maxn], dp[32][maxn];void init() { for (int i = 1; i <= n; i++) dp[0][i] = a[i]; int len = (int)log2(n)+1; for (int i = 1; i <= len; i++) { for (int j = 1; j <= n; j++) { if (j+(1<<(i-1)) <= n) dp[i][j] = max(dp[i-1][j], dp[i-1][j+(1<<(i-1))]); else dp[i][j] = dp[i-1][j]; } }}int query(int l, int r) { int k = (int)log2(r-l+1); return max(dp[k][l], dp[k][r-(1< r) ans = t-l; else ans = max(t-l, query(t, r)); printf("%d\n", ans); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。