FREQUENT-Frequent values

Frequent values

Given below c++ code for frequent spoj or frequent values spoj .

This question is simple implementation of segment tree so if you don,t know segment tree first read it and then try it. you can read it from HERE

More easy question on segment tree

BRCKTS

GSS3

HORRIBLE

GSS1

#include <bits/stdc++.h>
using namespace std;
struct node
{
  int res,pre,suf,pv,sv;
  void merge(node a,node b)
  {
    pre = a.pre;
    suf = b.suf;
    pv = a.pv;
    sv = b.sv;
    if(a.pv == b.pv )
      pre = a.pre + b.pre;
    if(a.sv == b.sv)
      suf = a.suf + b.suf;
    res = max(a.res,b.res);
    if(a.sv == b.pv)
      res = max(res , a.suf + b.pre);
  }
    node(){
      res = pre = suf = sv = pv = 0;
    }
    node(int val){
      res = pre = suf =1;
      sv = pv = val;
    }
}tree[500000];
void create(int pos)
{
  pos>>=1;
  while(pos){
    tree[pos].merge(tree[pos<<1],tree[(pos<<1)+1]);
    pos>>=1;
  }
}
node query(int root,int l_most,int r_most,int l,int r)
{
  if(l_most >= l && r_most <= r)
    return tree[root];
  int l_child = (root<<1) , r_child = l_child + 1,mid = (l_most + r_most )>>1;
  node left=node(),right = node();
  if(l<=mid)
    left = query(l_child,l_most,mid,l,r);
  if(r>mid)
    right = query(r_child,mid+1,r_most,l,r);;
  node temp = node();
  temp.merge(left,right);
  return temp;
}
int main()
{
  int n,q;
  while (1){
  scanf("%d",&n);
  if (n==0) break;
  scanf("%d",&q);
  int k = ceil(log(n)/log(2));
  int pos = (1<<k),temp;
  for(int i=0;i<n;i++){
    scanf("%d",&temp);
    tree[pos+i] = node(temp);
    create(pos+i);
  }
  for(int i=0;i<q;i++){
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d\n",query(1,1,pos,l,r).res);
  }}
  return 0;
}