题目链接:http://poj.org/problem?id=3368
题目意思:给出一段 n 个数的序列你,对于区间 [l, r] 的询问,找出 出现频率最高的数的次数。考虑到序列中的数是非递减的,也就是相同的数会连续不间断地在一起,于是就才有了代码中这个部分来预判了:
if (s > t)
printf("%d\n", ans);
这个人写RMQ 写得不错:http://dongxicheng.org/structure/lca-rmq/
这题就是套模板的,纪念第一个RMQ ^_^! 搞了整个晚上= =,懂了一点了,终于.......
详细请看代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; const int MAXN = 1e5 + ; int a[MAXN], b[MAXN];
int dp[MAXN][]; // dp[i][j] 实质对应别人的F[i, j] //dp[i][j]: 从 i 起连续2^j个数中的最大值
void makeRMQ(int n, int b[])
{
for (int i = ; i < n; i++)
{
dp[i][] = b[i];
// printf("dp[%d][0] = %d\n", i, dp[i][0]);
}
for (int j = ; (<<j) <= n; j++) // 2*j <= n
{
for (int i = ; i+(<<j)- < n; i++) // i+2*j-1 <= n
{
// printf("before: dp[%d][%d] = %d, dp[%d][%d] = %d\n", i, j-1, dp[i][j-1], i+(1<<(j-1)), j-1, dp[i+(1<<(j-1))][j-1]);
dp[i][j] = max(dp[i][j-], dp[i+(<<(j-))][j-]); // F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])
// printf("after: dp[%d][%d] = %d\n", i, j, dp[i][j]);
}
}
} int rmq(int s, int v)
{
int k = (int)(log(v-s+1.0) / log(2.0));
return max(dp[s][k], dp[v-(<<k)+][k]); // RMQ(A, i, j)=min{F[i,k],F[j-2^k+1,k]}
// k=[log2(j-i+1)]
} int find(int s, int t) // 找到序列a中(下标从0开始)和a[t](下标从1开始)值相同的第一个数(从左往右)的下标
{ // 例如对于 3 7, 返回的是6,因为a[7] = 3,和3相等的原始序列第一次出现3的时候下标是6(从0开始)
int tmp = a[t]; // 再例如对于2 6,返回的是2,因为a[6] = 1,第一次出现1的时候是下标2
int l = s;
int r = t;
while (l < r)
{
int mid = ((l+r)>>);
if (a[mid] >= tmp)
r = mid;
else
l = mid + ;
}
return r;
} int main()
{
int n, q, s, t;
while (scanf("%d", &n) != EOF && n)
{
scanf("%d", &q);
for (int i = ; i < n; i++)
scanf("%d", a+i);
int tmp;
for (int i = n-; i >= ; i--)
{
if (i == n-)
tmp = ;
else
{
if (a[i] == a[i+])
tmp++;
else
tmp = ;
}
b[i] = tmp; // 代表从后往前数,连续相同的数有多少个
}
makeRMQ(n, b);
while (q--)
{
scanf("%d%d", &s, &t);
s--, t--; // 下标从0开始
int tmp = find(s, t);
int ans = t - tmp + ;
t = tmp - ;
// printf("ans = %d, t = %d\n", ans, t);
if (s > t)
printf("%d\n", ans); // 这个区间只有连续的一段数,例如 [2, 6] 只有[1 1 1 1]
else
printf("%d\n", max(ans, rmq(s, t))); // 要从两段区间里找(详细看链接),因为这个区间有多个连续的一段数,例如[1, 10]有[1 1 1 1] 和[10 10 10]
}
}
return ;
}