Link to problem: https://www.spoj.com/problems/FREQUENT/↵
↵
I know this is quite a famous problem and I have searched extensively about it , but my attempts at debugging my code have failed. ↵
↵
I use the approach of Segment Trees to solve this problem after having built a frequency array.↵
Run time : $O(n)$ pre-processing per test case and $O(log (n))$ to answer each query.↵
↵
~~~~~↵
#include<iostream>↵
#include<algorithm>↵
#include<unordered_map>↵
↵
using namespace std;↵
↵
const int N=200000;↵
↵
int a[N],t[4*N],b[N]; //b is the frequency array↵
↵
void build(int v,int tl,int tr){↵
if(tl==tr){↵
t[v]=b[tl];↵
}↵
else{↵
int tm=(tl+tr)/2;↵
build(2*v,tl,tm);↵
build(2*v+1,tm+1,tr);↵
t[v]=max(t[2*v],t[2*v+1]);↵
}↵
}↵
↵
int query(int v,int tl,int tr,int l,int r){↵
if(l>r)↵
return -1e9;↵
if(l<=tl&&tr<=r)↵
return t[v];↵
int tm=(tl+tr)/2;↵
return max(query(v*2, tl, tm, l, min(r, tm)),↵
query(v*2+1, tm+1, tr, max(l, tm+1), r));↵
}↵
int main()↵
{↵
int n,q; ↵
while(true){↵
scanf("%d", &n);↵
if(!n)break;↵
scanf("%d", &q);↵
unordered_map<int,int>cnt;↵
for(int i=0;i<n;i++){↵
scanf("%d",&a[i]);↵
++cnt[a[i]];↵
}↵
for(int i=0;i<n;i++){↵
b[i]=cnt[a[i]];↵
}↵
build(1,0,n-1);↵
while(q--){↵
int l,r;↵
scanf("%d %d",&l,&r);↵
--l,--r;↵
if(a[r]==a[l]){ //This is when all numbers in the range are the same.↵
printf("%d\n",r-l+1);↵
}↵
else{↵
/*This is to handle the case as follows :111 22233 4444↵
idx1 and idx2-1 will cover the range 22233 and↵
then we do the max of all three blocks [111] [22233] [4444] which↵
in this case is basically max(3,3,4)=4 */↵
int idx1=upper_bound(a+l,a+l+r,a[l])-a;↵
int idx2=lower_bound(a+l,a+l+r,a[r])-a;↵
int ans=max(max(idx1-l,r+1-idx2),query(1,0,n-1,idx1,idx2-1));↵
printf("%d\n",ans);↵
}↵
}↵
}↵
return 0;↵
} ↵
~~~~~↵
↵
↵
↵
↵
I know this is quite a famous problem and I have searched extensively about it , but my attempts at debugging my code have failed. ↵
↵
I use the approach of Segment Trees to solve this problem after having built a frequency array.↵
Run time : $O(n)$ pre-processing per test case and $O(log (n))$ to answer each query.↵
↵
~~~~~↵
#include<iostream>↵
#include<algorithm>↵
#include<unordered_map>↵
↵
using namespace std;↵
↵
const int N=200000;↵
↵
int a[N],t[4*N],b[N]; //b is the frequency array↵
↵
void build(int v,int tl,int tr){↵
if(tl==tr){↵
t[v]=b[tl];↵
}↵
else{↵
int tm=(tl+tr)/2;↵
build(2*v,tl,tm);↵
build(2*v+1,tm+1,tr);↵
t[v]=max(t[2*v],t[2*v+1]);↵
}↵
}↵
↵
int query(int v,int tl,int tr,int l,int r){↵
if(l>r)↵
return -1e9;↵
if(l<=tl&&tr<=r)↵
return t[v];↵
int tm=(tl+tr)/2;↵
return max(query(v*2, tl, tm, l, min(r, tm)),↵
query(v*2+1, tm+1, tr, max(l, tm+1), r));↵
}↵
int main()↵
{↵
int n,q; ↵
while(true){↵
scanf("%d", &n);↵
if(!n)break;↵
scanf("%d", &q);↵
unordered_map<int,int>cnt;↵
for(int i=0;i<n;i++){↵
scanf("%d",&a[i]);↵
++cnt[a[i]];↵
}↵
for(int i=0;i<n;i++){↵
b[i]=cnt[a[i]];↵
}↵
build(1,0,n-1);↵
while(q--){↵
int l,r;↵
scanf("%d %d",&l,&r);↵
--l,--r;↵
if(a[r]==a[l]){ //This is when all numbers in the range are the same.↵
printf("%d\n",r-l+1);↵
}↵
else{↵
/*This is to handle the case as follows :111 22233 4444↵
idx1 and idx2-1 will cover the range 22233 and↵
then we do the max of all three blocks [111] [22233] [4444] which↵
in this case is basically max(3,3,4)=4 */↵
int idx1=upper_bound(a+l,a+l+r,a[l])-a;↵
int idx2=lower_bound(a+l,a+l+r,a[r])-a;↵
int ans=max(max(idx1-l,r+1-idx2),query(1,0,n-1,idx1,idx2-1));↵
printf("%d\n",ans);↵
}↵
}↵
}↵
return 0;↵
} ↵
~~~~~↵
↵
↵
↵