OI

POJ 3368 Frequent values

Description

You are given a sequence of n integers a1 , a2 , … , an 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 ai , … , aj.

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 a1 , … , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, …, n}) separated by spaces. You can assume that for each i ∈ {1, …, n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (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

1
2
3
4
5
6

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

Sample Output

1
2
3

1
4
3

Solution

水题！

原谅我刷这么水的题目…

既然他是单增序列，不妨我们用两个数字记录每个数字是几和这个数字出现次数。

然后跑区间最大就可以了，注意，类似于分块的，左右端点在两个块内，注意一下细节。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <cstdio>
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; c < '0' || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r=r*10-'0'+c;
	return r * k;
}
const int maxn = 100005;
const int INF = 1000000007;
int n, m, mi[maxn<<2], mx[maxn<<2];
int a[maxn], b[maxn], L[maxn], R[maxn], pos[maxn], tot;
int min(int a, int b) {
	return a < b ? a : b;
}
int max(int a, int b) {
	return a > b ? a : b;
}
void build(int now, int l, int r) {
	if (l == r) {
		mx[now] = mi[now] = R[l]-L[l]+1;
		return;
	}
	int mid = (l + r) >> 1;
	build(now<<1,l,mid); build(now << 1 | 1, mid+1, r);
	mi[now] = min(mi[now<<1], mi[now<<1|1]);
	mx[now] = max(mx[now<<1], mx[now<<1|1]);
}
int miq(int now, int l, int r, int ll, int rr) {
	if (ll <= l && r <= rr) return mi[now];
	int mid = (l+r)>>1;
	int ret = INF;
	if (ll <= mid) ret = min(ret, miq(now<<1,l,mid, ll, rr));
	if (rr > mid ) ret = min(ret, miq(now<<1|1,mid+1,r,ll,rr));
	return ret;
}
int mxq(int now, int l, int r, int ll, int rr) {
	if (ll <= l && r <= rr) return mx[now];
	int mid = (l+r)>>1;
	int ret = -INF;
	if (ll <= mid) ret = max(ret, mxq(now<<1,l,mid, ll, rr));
	if (rr > mid ) ret = max(ret, mxq(now<<1|1,mid+1,r,ll,rr));
	return ret;
}
int main() {
	while (true) {
		n = getint();
		if (n == 0) break;
		m = getint();
		tot = 0;
		for (int i = 1; i <= n; ++i) a[i] = getint();
		int lst = -100002;
		for (int i = 1; i <= n; ++i) {
			if (lst != a[i]) {
				lst = a[i];
				++tot;
				pos[i] = tot;
				b[tot] = lst;
				L[tot] = i;
				R[tot] = i;
			} else {
				R[tot] = i;
				pos[i] = tot;
			}
		}
		build(1, 1, tot);
		int x, y;
		while (m--) {
			x = getint(); y = getint();
			if (pos[x] == pos[y])
				printf("%d\n", y-x+1);
			else {
			int ans = 0;
			ans = max(ans, R[pos[x]]-x+1);
			ans = max(ans, y-L[pos[y]]+1);
			if (pos[x]+1 <= pos[y]-1)
				ans = max(ans, mxq(1,1,tot,pos[x]+1,pos[y]-1));
			printf("%d\n", ans);
			}
		}
	}
}