Frequent values
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)
Total Submission(s) : 25 Accepted Submission(s) : 11
Problem 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
<p>The input consists of several test cases. Each test case starts with a line containing two integers <strong>n</strong> and <strong>q</strong> (<i>1 ≤ n, q ≤ 100000</i>). The next line contains <strong>n</strong> integers <strong>a<sub>1</sub> , ... , a<sub>n</sub></strong> (<i>-100000 ≤ a<sub>i</sub> ≤ 100000</i>, for each <i>i ∈ {1, ..., n}</i>) separated by spaces. You can assume that for each <i>i ∈ {1, ..., n-1}: a<sub>i</sub> ≤ a<sub>i+1</sub></i>. The following <strong>q</strong> lines contain one query each, consisting of two integers <strong>i</strong> and <strong>j</strong> (<i>1 ≤ i ≤ j ≤ n</i>), which indicate the boundary indices for the <br>query.</p><p>The last test case is followed by a line containing a single <i>0</i>.</p>
Output
<p>For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.</p>
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
PKU
区间求最大值，插入点易错点很多。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
int a[100010];
int ans;
struct node
{
int l,r;
int lcnt,ln,rcnt,rn;
int cnt,num;
}t[100010<<2];
void build(int l,int r,int n)
{
t[n].l=l;
t[n].r=r;
if(l==r)
{
t[n].cnt=t[n].lcnt=t[n].rcnt=1;
t[n].num=t[n].ln=t[n].rn=a[l];
return;
}
int m=(l+r)>>1;
build(l,m,n<<1);
build(m+1,r,n<<1|1);
if(t[n<<1].cnt>=t[n<<1|1].cnt){
t[n].cnt=t[n<<1].cnt;
t[n].num=t[n<<1].num;
}
else{
t[n].cnt=t[n<<1|1].cnt;
t[n].num=t[n<<1|1].num;
}
t[n].lcnt=t[n<<1].lcnt;
t[n].rcnt=t[n<<1|1].rcnt;
t[n].ln=t[n<<1].ln;
t[n].rn=t[n<<1|1].rn;
if(t[n<<1].rn==t[n<<1|1].ln)
{
if(t[n<<1].rcnt+t[n<<1|1].lcnt>t[n].cnt)
{
t[n].cnt=t[n<<1].rcnt+t[n<<1|1].lcnt;
t[n].num=t[n<<1|1].ln;
}
if(t[n<<1].rn==t[n<<1|1].rn){
t[n].rcnt+=t[n<<1].rcnt;
}
if(t[n<<1|1].ln==t[n<<1].ln){
t[n].lcnt+=t[n<<1|1].lcnt;
}
}
}
void query(int l,int r,int n)
{
if(t[n].l==l&&t[n].r==r){
ans=max(t[n].cnt,ans);
return;
}
if(l>=t[n<<1|1].l){
query(l,r,n<<1|1);
}
else if(r<=t[n<<1].r){
query(l,r,n<<1);
}
else{
query(l,t[n<<1].r,n<<1);
query(t[n<<1|1].l,r,n<<1|1);
if(t[n<<1].rn == t[n<<1|1].ln)
{
int ans1=0,ans2=0;
if(a[l]!=t[n<<1].rn)
ans1=t[n<<1].rcnt;
else ans1=t[n<<1].r-l+1;
if(a[r]!=t[n<<1|1].ln)
ans2=t[n<<1|1].lcnt;
else ans2=r-t[n<<1].r;
ans=max(ans,ans1+ans2);
return ;
}
}
}
int main()
{
int n,q;
while(scanf("%d",&n),n)
{
scanf("%d",&q);
for(int i =1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,n,1);
for(int i = 0;i<q;i++){
int x,y;
scanf("%d%d",&x,&y);
if(x==y){
puts("1");
continue;
}
ans=0;
query(x,y,1);
cout<<ans<<endl;
}
}
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
