2013
12-23

# Frequent values

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 .

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.

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

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

1
4
3

Hint
A naive algorithm may not run in time!


上面的过程有个问题，如果区间的开始和结束的那个数所在的连续区间被切断，比如1,1,3,3,3,5，然后让我们询问【2，3】，那1被切断了，3被切断了，上面的方法似乎就不靠谱了，怎么办？把前后拿出来单独计算就好，计算时与这个数所在的区间头区间尾比较找出有多少个在询问的区间内就好。然后取区间头、区间中、区间尾的最大值即可ac。

10 7
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
1 2
3 6
7 7
8 10

5 5
1 2 3 4 5
1 1
5 5
1 3
2 4
1 5

#include <stdio.h>
#include <string.h>
#include <map>
#include <math.h>
using namespace std;
#define MAX 110000
#define max(a,b) (a)>(b)?(a):(b)

map<int ,int> mmap;
int n,m,arr[MAX],tot,ans;
struct node {

int v,beg,end,cnt;
}brr[MAX*2];
struct RMQ {

int  dp[MAX][18];
void Create();
int  Query(int l,int r);
}rmq;
void RMQ::Create() {

int i,j;
for (i = 1; i <= tot; ++i)
dp[i][0] = brr[i].cnt;
for (j = 1; (1<<j) <= n; ++j)
for (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::Query(int l, int r){

int k = (int)(log(r-l+1.0)/log(2.0));
return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
int GetHash(int x,int in) {

//if (x < 0) return x + 100001;
//else return x;
if (mmap.find(x) == mmap.end()) {

mmap[x] = ++tot;
brr[tot].v = x;
brr[tot].beg = in;
brr[tot].cnt = 0;
brr[tot-1].end = in - 1;
}
return mmap[x];
}

int main()
{
int i,j,k,ta,tb,tc,a,b;

while (scanf("%d",&n),n) {

scanf("%d",&m);
tot = 0,mmap.clear();
for (i = 1; i <= n; ++i){

scanf("%d",&arr[i]);
k = GetHash(arr[i],i);
brr[k].cnt++;
}
brr[tot].end = n;

rmq.Create();
for (i = 1; i <= m; ++i) {

scanf("%d%d",&a,&b);
if (arr[a] != arr[b]) {

j = GetHash(arr[a],i);
ta = brr[j].end - a + 1;    //获取前面一段的长度，可不进行查询
k = GetHash(arr[b],i);
tb = b - brr[k].beg + 1;    //获取后面一段的长度，可不进行查询
ans = max(ta, tb);
if (brr[j].end + 1 != brr[k].beg) {
//中间还有一些区间,必须查询
tc = rmq.Query(j + 1, k - 1);
ans = max(tc, ans);
}
}
else ans = b - a + 1;
printf("%d\n",ans);
}
}
}