题目大意:一个非降序序列,有若干查询,每次查询一个区间中重复次数最多的数字的个数。
思路:因为是非降序的,所以可以从头遍历把每个相同的数字划为一个块,用p[i]表示ai划分到了哪个块里面,同时还可以记录每个块的左右边界。同时还可以获得每块中数字的个数。可以把这些个数处理成ST表。
对于每个给定的查询区间,如果区间完全包含于某一个块内,那么说明区间内所有数字相同,答案就是区间的长度。否则,该查询区间可以分为3个部分:1)左侧[l,r[p[l]]的一个块的部分,2)左右侧[l[p[r],r]的另一个块的部分,以及3)中间的若干完整的块。其中1),2)中重复数字的数量分别就是他们的区间长度,而3)的部分可以通过ST表用RMQ求得,答案就是这三者取最大值。
代码:
//POJ.3368
//Author: Prgl
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
//ST表,各段数字出现次数,第i个数字位于第几段,段的左右界(左闭右开)
int b[100010][30], freq[100010], p[100010], l[100010], r[100010];
void RMQ_init(int n)
{
for (int i = 0; i < n; i++)
b[i][0] = freq[i];
for (int j = 1; (1 << j) <= n; j++)
{
for (int i = 0; i + (1 << j) - 1 < n; i++)
b[i][j] = max(b[i][j - 1], b[i + (1 << (j - 1))][j - 1]);
}
}
int RMQ(int l, int r)
{
int k = 0;
if (l >= r)
return 0;
while (1 << (k + 1) < r - l)
k++;
return max(b[l][k], b[r - (1 << k)][k]);
}
int N, Q;
void solve()
{
memset(freq, 0, sizeof(freq));
int num, last;
int index = 0;
for (int i = 0; i < N; i++)
{
cin >> num;
if (i == 0)
{
last = num;
freq[index]++;
l[0] = 0;
}
else
{
if (num == last)
{
freq[index]++;
}
else
{
last = num;
r[index++] = i;
freq[index]++;
l[index] = i;
}
}
p[i] = index;
}
r[index] = N;
RMQ_init(index + 1);
int ql, qr, ans, lo, hi;
for (int i = 0; i < Q; i++)
{
scanf("%d%d", &lo, &hi);
ql = lo - 1;
qr = hi - 1;
if (p[ql] == p[qr])
ans = qr - ql + 1;
else
{
int a = r[p[ql]] - ql;
int b = qr - l[p[qr]] + 1;
int c = RMQ(p[ql] + 1, p[qr]);
ans = max(a, max(b, c));
}
printf("%d\n", ans);
}
}
int main()
{
scanf("%d", &N);
while (N != 0)
{
scanf("%d", &Q);
solve();
scanf("%d", &N);
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章