POJ 3368 Frequent values 解题报告

dianlujitao 无回复

Time Limit: 2000MS

Memory Limit: 65536KB

64bit IO Format: %lld & %llu

Description

You are given a sequence of n integers a₁ , a₂ , … , a_n in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers a_i , … , a_j.

Input

The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a₁ , … , a_n (-100000 ≤ a_i ≤ 100000, for each i ∈ {1, …, n}) separated by spaces. You can assume that for each i ∈ {1, …, n-1}: a_i ≤ a_i+1. The following q lines contain one query each, consisting of two integers i andj (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the
query.

The last test case is followed by a line containing a single 0.

Output

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

Sample Input

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

10 3

-1 -1 1 1 1 1 3 10 10 10

2 3

1 10

5 10

Sample Output

1
4
3

Source

Ulm Local 2007

题目大意为给出一个n个数的不下降数列，然后有q个询问，求给定区间内出现最多的数的次数。由于数列是不下降的，相同的数必然挨在一起，这个数列边自然分成了若干块，并且每块中的数都相等。令f[n]为第n个数在块中的编号，如样例f[1]=1, f[2]=2, f[3]=1, f[4]=2, f[5]=3……

预处理完成后考虑一种特殊情况，如果询问给定的区间的左端点恰好是一个块的左端点的话，对f数组用RMQ求区间最大值即可。回到一般情况，左端点在一个块的中间怎么办？直接从左端点开始往右扫到下一个块为止，剩余部分便是特殊情况，RMQ解决，然后跟左边的比较，取最大值即为答案。

AC代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 10;
int a[maxn], f[maxn];
int dp[maxn][20], mm[maxn];
void initrmq(int n, int b[])
{
	mm[0] = -1;
	for (int i = 1; i <= n; i++)
	{
		mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
		dp[i][0] = b[i];
	}
	for (int j = 1; j <= mm[n]; j++)
		for (int i = 1; i + (1 << j) - 1 <= n; i++)
			dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
int rmq(int x, int y)
{
	int k = mm[y - x + 1];
	return max(dp[x][k], dp[y - (1 << k) + 1][k]);
}
int main()
{
	int n, q;
	while (scanf("%d%d", &n, &q) == 2)
	{
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		int l, r;
		f[1] = 1;
		for (int i = 2; i <= n; i++)
			f[i] = (a[i] == a[i - 1]) ? f[i - 1] + 1 : 1;
		initrmq(n, f);
		while (q--)
		{
			scanf("%d%d", &l, &r);
			int tmp = 0, pos = l;
			while (pos <= r && a[pos] == a[pos - 1])
				pos++, tmp++;
			printf("%d\n", max(tmp, rmq(pos, r)));
		}
	}
	return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn = 100000 + 10;

int a[maxn], f[maxn];

int dp[maxn][20], mm[maxn];

void initrmq(int n, int b[])

{

mm[0] = -1;

for (int i = 1; i <= n; i++)

{

mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];

dp[i][0] = b[i];

}

for (int j = 1; j <= mm[n]; j++)

for (int i = 1; i + (1 << j) - 1 <= n; i++)

dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);

}

int rmq(int x, int y)

{

int k = mm[y - x + 1];

return max(dp[x][k], dp[y - (1 << k) + 1][k]);

}

int main()

{

int n, q;

while (scanf("%d%d", &n, &q) == 2)

{

for (int i = 1; i <= n; i++)

scanf("%d", &a[i]);

int l, r;

f[1] = 1;

for (int i = 2; i <= n; i++)

f[i] = (a[i] == a[i - 1]) ? f[i - 1] + 1 : 1;

initrmq(n, f);

while (q--)

{

scanf("%d%d", &l, &r);

int tmp = 0, pos = l;

while (pos <= r && a[pos] == a[pos - 1])

pos++, tmp++;

printf("%d\n", max(tmp, rmq(pos, r)));

}

return 0;

}

Dianlujitao's Space

POJ 3368 Frequent values 解题报告

来一发吐槽撤销评论

来一发吐槽 撤销评论

来一发吐槽撤销评论