Hi, please help me with <a href="http://www.spoj.com/problems/FREQUENT/">this</a> problem I'm stuck from many days. I've done it many times but it verdicts WRONG ANSWER. I've tried it again and again with my own custom test input and it generates right answer. Please help me through this
I'm using a segment tree to solve this problem
Every node of my segment tree stroes:
1.size : size of the part of array it stores
2.pair<int,int> left:
left.val: value of best repeated element in left part of range
left.freq: it's frequency
3.pair<int,int> right:
right.val and right.freq similar to above
4.pair<int,int> best:
best.val: most repeated element in range
best.freq: its frequency
My idea:
my most repeated element in a given range can be found in either
-left child or
-right child of tree or
-if arr[mid]==arr[mid+1] then it may lie in both
some functions in my code are:
build(): to build the tree
query(): for querying the tree
init(): to initialize leaf nodes
merge(): to merge left child and right child
please help me. I'll be very thankfull to you
My Code:
include
define val first
define freq second
define lc(x) (2*x)
define rc(x) (2*x+1)
using namespace std;
int n,arr[100000];
typedef struct fr{
pair left,right,best;
int size;
fr(){}
fr(int x){
left.freq=right.freq=best.freq=size=x;
}
}node;
node waste(-1);
node tree[400000];
void init(node &baby,int v){
baby.left.val=baby.right.val=baby.best.val=v;
baby.left.freq=baby.right.freq=baby.best.freq=1;
baby.size=1;
}
void merge(node &big,node L,node R){
big.size=L.size+R.size;
if( L.left.freq==L.size and R.left.val==L.right.val ){
big.left.val=L.left.val;
big.left.freq=L.size+R.left.freq;
}
else
big.left=L.left;
if( R.right.freq==R.size and L.right.val==R.left.val ){
big.right.val=R.right.val;
big.right.freq=R.size+L.right.freq;
}
else
big.right=R.right;
big.best.freq=0;
if( L.right.val==R.left.val ){
big.best.val=L.right.val;
big.best.freq=L.right.freq+R.left.freq;
}
if( big.best.freq<L.best.freq ) big.best=L.best;
if( big.best.freq<R.best.freq ) big.best=R.best;
}
void build(int curnode,int start,int end){
if( start==end )
init(tree[curnode],arr[start]);
else{
int mid=(start+end)/2;
build(lc(curnode),start,mid);
build(rc(curnode),mid+1,end);
merge(tree[curnode],tree[lc(curnode)],tree[rc(curnode)]);
}
}
node query(int curnode,int start,int end,int l,int r){
if( r<start or end<l ) return waste;
if( l<=start and end<=r ) return tree[curnode];
int mid=(start+end)/2;
node L=query((2*curnode),start,mid,l,r);
node R=query((2*curnode+1),mid+1,end,l,r);
if( L.best.freq==-1 ) return R;
if( R.best.freq==-1 ) return L;
node res;
merge(res,L,R);
return res;
}
int main(void){
scanf("%d",&n);
int q; scanf("%d",&q);
for(int i=0;i<n;i++) scanf("%d",&arr[i]);
build(1,0,n-1);
while(q--){
int a; scanf("%d",&a);
int b; scanf("%d",&b);
--a;
--b;
printf("%d\n",query(1,0,n-1,a,b).best.freq);
}
}