当前位置 : 主页 > 编程语言 > java >

Frequent values (线段树)

来源:互联网 收集:自由互联 发布时间:2022-08-15
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 amo


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.
Note: A naive algorithm may not run in time!
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

题目大概:

给出n个整数,求区间l,r之间的最多相同元素的数量,这n个整数满足(ai<=aj)当 i<=j 时。

思路:

看到这个题,就想把相同的元素合并成一个点,值为这个元素的数量,求最大相同元素个数,就是求最值。这样就转化为一个简单的线段树求区间最值的问题了。但是这个区间的端点需要特殊考虑一下,因为求得区间不一定是刚好是在每个元素的分界线上。这样,当区间很小时,也需要特殊考虑一下。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
int Map[maxn];
int a[maxn],b[maxn],c[maxn];
int sum[maxn<<3];
int cnt;
void pushup(int rt)
{
sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}

void build(int l,int r,int rt)
{
if(l==r)
{
sum[rt]=a[++cnt];
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}

int quert(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return sum[rt];
}

int m=(l+r)>>1;
int ret=0;
if(L<=m)ret=max(ret,quert(L,R,lson));
if(R>m)ret=max(ret,quert(L,R,rson));

return ret;
}
int main()
{
int n,m;
while(~scanf("%d",&n)&&n)
{
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
memset(Map,0,sizeof(Map));
memset(b,0,sizeof(b));
memset(sum,0,sizeof(sum));
scanf("%d",&m);
int u;
cnt=0;
int pre=INF;
int ans=0;
for(int i=1; i<=n; i++)
{
scanf("%d",&u);
b[i]=u;
if(u==pre)
{
Map[i]=ans;
a[ans]++;
c[i]=c[i-1]+1;
}
else
{
Map[i]=++ans;
a[ans]++;
c[i]=1;
}
pre=u;
}
build(1,ans,1);
int l,r;
for(int i=1; i<=m; i++)
{
scanf("%d%d",&l,&r);
if(Map[l]==Map[r]) //区间只有一个点
{
printf("%d\n",r-l+1);
}
else if(Map[r]-Map[l]==1)//区间有两个点,不需要用线段树
{
printf("%d\n",max((a[Map[l]]-c[l]+1),c[r]));
}
else //区间有3个点以上,中间的点需要用线段树,两端特殊处理。
{
int max_1=quert(Map[l]+1,Map[r]-1,1,ans,1);
int max_2=a[Map[l]]-c[l]+1;
int max_3=c[r];
int ma=max(max_1,max(max_2,max_3));
printf("%d\n",ma);
}
}
}
return 0;
}




上一篇:HDU 4372:Count the Buildings (Stirling数)
下一篇:没有了
网友评论