| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 13516 | Accepted: 4971 |
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
由于是非递减数列。同样的元素必须是连在一块的。能够统计不同元素的个数，以元素的个数建树，给出一段区间，再二分查找出如今第几个元素，特殊考虑最前和最后，中间的用线段树。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=100000+100;
int p;
int tree[maxn<<2];
int num[maxn],sum[maxn];
int a[maxn];
void build(int rt,int l,int r)
{
if(l==r)
{
tree[rt]=num[l];
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
int query(int rt,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
{
return tree[rt];
}
int ans=0;
int mid=(l+r)>>1;
if(L<=mid)
ans=query(rt<<1,l,mid,L,R);
if(R>mid)
ans=max(ans,query(rt<<1|1,mid+1,r,L,R));
return ans;
} int find(int k)
{
int l=1,r=p;
int m;
while (l<=r)
{
m=(l+r)>>1;
if(k>sum[m])
l=m+1;
else if(k<sum[m])
r=m-1;
else
break;
}
if(sum[m-1]>=k)
return m-1;
else if(sum[m]>=k)
return m;
else
return m+1;
}
int main()
{
int n,m;
while(~scanf("%d",&n)&&n)
{
memset(num,0,sizeof(num));
memset(sum,0,sizeof(sum));
memset(tree,0,sizeof(tree));
scanf("%d",&m);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int temp;
temp=0;
p=1;
num[p]=1;
sum[0]=0;
for(int i=1;i<n;i++)
{
if(a[temp]==a[i])
{
num[p]++;
}
else
{
temp=i;
sum[p]=sum[p-1]+num[p];
p++;
num[p]=1;
}
}
sum[p]=sum[p-1]+num[p];
build(1,1,p);
int l,r;
for(int i=0;i<m;i++)
{
int u,v;
int ans=0;
scanf("%d%d",&l,&r);
u=find(l);
v=find(r);
ans=sum[u]-l+1;
if(u==v)
{
printf("%d\n",r-l+1);
continue;
}
if(u+1<=v-1)
ans=max(ans,query(1,1,p,u+1,v-1));
ans=max(ans,r-sum[v-1]);
printf("%d\n",ans);
}
}
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。