Language: Frequent values Time Limit: 2000MSMemory Limit: 65536K Total Submissions: 14377Accepted: 5244
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
10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0
Sample Output
1 4 3
Source Ulm Local 2007
根据题目的意思,相同的数字都是放在一起的,所以我们把相同的数字看成一组,每次查询都找出所在的组,然后去掉零头单独处理,中间完整部分用rmq来查,复杂度
/************************************************************************* > File Name: POJ3368.cpp > Author: ALex > Mail: zchao1995@gmail.com > Created Time: 2015年04月23日 星期四 21时37分21秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;const int N = 100010;int num[N];int arr[N];int arrarr[N];int mp[N], mp2[N], L[N], zu[N];int dp[N][20];int LOG[N];void initRMQ(int n) {for (int i = 1; i <= n; ++i) {dp[i][0] = num[i];}for (int j = 1; j <= LOG[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 ST(int a, int b) {int k = LOG[b – a + 1];return max(dp[a][k], dp[b – (1 << k) + 1][k]);}int main() {LOG[0] = -1;for (int i = 1; i <= 100000; ++i) {LOG[i] = (i & (i – 1)) ? LOG[i – 1] : LOG[i – 1] + 1;}int n, q;while (~scanf(“%d”, &n), n) {scanf(“%d”, &q);for (int i = 1; i <= n; ++i) {scanf(“%d”, &arrarr[i]);}int cnt = 1;arr[1] = 1;for (int i = 1; i <= n; ++i) {if (arrarr[i] == arrarr[i – 1]) {arr[i] = arr[i – 1];}else {arr[i] = ++cnt;}}memset(num, 0, sizeof(num));mp[arr[1]] = -inf;L[arr[1]] = 1;zu[arr[1]] = 1;num[1] = 1;cnt = 1;for (int i = 2; i <= n; ++i) {if(arr[i] == arr[i – 1]) {++num[cnt];}else {++cnt;zu[arr[i]] = i;L[arr[i]] = cnt;mp[arr[i]] = arr[i – 1];mp2[arr[i – 1]] = arr[i];num[cnt] = 1; //第i组数目}}mp2[arr[n]] = -inf;int l, r;initRMQ(cnt);while (q–) {scanf(“%d%d”, &l, &r);if (arr[l] == arr[r]) {printf(“%d\n”, r – l + 1);continue;}int nxt = mp2[arr[l]];int pos1 = zu[nxt];int cnt1 = pos1 – l;int last = mp[arr[r]];int pos2 = zu[arr[r]];int cnt2 = r – pos2 + 1;pos1 = L[nxt];pos2 = L[last];//printf(“%d %d %d %d\n”, cnt1, cnt2, pos1, pos2);if (pos1 > pos2) {printf(“%d\n”, max(cnt1, cnt2));}else {printf(“%d\n”, max(cnt1, max(cnt2, ST(pos1, pos2))));}}}return 0;}
，或许是某个未开发的荒凉小岛，或许是某座闻名遐迩的文化古城。
