| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 4913 | Accepted: 1728 |
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
很显然，这题要用离散化，首先将原始数组a[1..n]，变成另外一个数组b[1..k]，b[i]表示a数组中第i种数的个数（显然k<=n），再用一个数组c[1..k]来记录数组b的前i项和，求频率最高数的时候，我们只要理清所要查询的区间中含有多少个完整的b[i]，求出这些b[i]中的最大值，再于两端边界比较，就能得到结果了。
就拿样例来说，这时a[]={0,-1,-1,1,1,1,1,3,10,10,10}，b[]={0,2,4,1,3}，c[]={0,2,6,7,10}，k=4；
当查询5 10时，通过对c数组的查询可以得到有两个完整的b[i]，就是b[3]=1,b[4]=3，这两个中的最大值是3，再处理边界情况，a[5]到a[6]有两个1，比3小，故可得结果为3。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100000;
struct node
{
int left,right;
int maxlen;
}t[N*3];
int dia[N+100];
int b[N+100];
int c[N+100];
inline int Max(int a,int b)
{
return a>b?a:b;
}
void maketree(int c,int l,int r)
{
t[c].left = l;
t[c].right = r;
if(l==r)
{
t[c].maxlen = b[l];
return ;
}
int mid = (l+r)>>1;
maketree(c*2,l,mid);
maketree(c*2+1,mid+1,r);
t[c].maxlen = Max( t[c*2].maxlen , t[c*2+1].maxlen);
}
int findans(int c,int l,int r)
{
if(t[c].left == l && t[c].right == r)
return t[c].maxlen;
int mid = (t[c].right+t[c].left)>>1;
if(mid >= r)
return findans(c*2,l,r);
else if(mid < l)
return findans(c*2+1,l,r);
else
return Max(findans(c*2,l,mid),findans(c*2+1,mid+1,r));
}
int main()
{
int n,i,j;
int q;
int s,e;
int index;
while(cin>>n,n)
{
cin >> q;
for(i=1;i<=n;i++)
scanf("%d",&dia[i]);
b[1] = 1;
index = 1;
c[0] = 0;
for(i=2;i<=n;i++)
{
while(i<=n && dia[i] == dia[i-1])
{
i ++;
b[index] ++;
}
if(i<=n)
{
c[index] = c[index-1] + b[index];
b[++index] = 1;
}
}
c[index] = c[index-1] + b[index];
c[index+1] = 100001;
maketree(1,1,index);
while(q --)
{
scanf("%d%d",&s,&e);
int beg = lower_bound(c,c+index+1,s) - c;
int end = lower_bound(c,c+index+1,e) - c - 1;
if(beg>end)
printf("%d/n",e-s+1);
else if(beg==end)
printf("%d/n",Max(c[beg]-s+1,e-c[beg]));
else
{
int ma = findans(1,beg+1,end);
ma = Max(ma,c[beg]-s+1);
ma = Max(ma,e-c[end]);
printf("%d/n",ma);
}
}
}
return 0;
}
RMQ(Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在[i,j]里的最小(大）值。这里有两种较优的方法，一是上面写的线段树求法，二是没学过的动态规划ST算法（Sparse Table）。先简要介绍一下ST算法：以求最大值为例，设d[i,j]表示[i,i+2^j-1]这个区间内的最大值，那么在询问到[a,b]区间的最大值时答案就是max(d[a,k], d[b-2^k+1,k])，其中k是满足2^k<=b-a的最大的k,即k=[ln(b-a+1)/ln(2)]，d的求法可以用动态规划，d[i,j]=max(d[i,j-1],d[i+2^(j-1),j-1])（摘自百度百科）。
/*
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAX 100010
//#define Max(a,b) (a>b?a:b)
inline int Max(int a,int b)
{
return a>b?a:b;
}
int a[MAX],b[MAX][20],c[MAX];
void make(int n)
{
int k=(int)(log(n*1.0)/log(2.0));
for(int j=1;j<=k;j++){
for(int i=1;i<=n-(1<<j)+1;i++){
b[i][j]=Max(b[i][j-1],b[i+(1<<(j-1))][j-1]);//[i,i+2^(j)-1]中的最大值
}
}
}
int search(int i,int j)
{
int k=(int)(log(j-i+1.0)/log(2.0));
int rmq=Max(b[i][k], b[j - (1 <<k) + 1][k]);
return rmq;
}
int main()
{
int n,q,x,y,k;
while(scanf("%d",&n),n>0){
scanf("%d",&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
b[1][0]=1,x=a[1],k=1;
for(int i=2;i<=n;i++){
if(x==a[i]){
b[k][0]++;
}
else {
b[++k][0]=1;
x=a[i];
}
}
make(k);
c[0]=0;
for(int i=1;i<=k;i++){
c[i]=c[i-1]+b[i][0];//c[i]记录的是[b[1][0],b[i][0]]之间的数之和。
}//c[i]包括b[i][0]了！
c[++k]=100001;
for(int i=0;i<q;i++){
scanf("%d%d",&x,&y);
int tempi = std::lower_bound(c,c+k+1,x-1) - c +1 ;
int tempj = std::lower_bound(c,c+k+1,y+1) - c- 1;
if(tempi>tempj+1){//在一个区间内，即在同个b[x][0]内！x=tempi-1 = tempj +1;
printf("%d/n",y-x+1);
}
else if(tempi==tempj+1){//在相邻的两个区间内，取最大值！分别位于b[tempj][0]与b[tempi][0]里；
printf("%d/n",Max(c[tempj]-x+1,y-c[tempj]));
}
else {
int max = search(tempi,tempj);//在b[i][k],与b[j][k]中取最大值，k=(int)(log(n*1.0)/log(2.0));
max = Max(max,c[tempi-1]-x+1);
max = Max(max,y-c[tempj]);
printf("%d/n",max);
}
}
}
}
*/参考http://hustsxh.is-programmer.com/posts/10874.html