for this problem: http://www.spoj.pl/problems/PATULJCI/

i have got some idea from this analysis by COCI. http://hsin.hr/coci/archive/2009_2010/contest3_solutions.zip

so far my implementation is with segment tree, then binary search.

here is my implementation which is getting WA:

/* Bismillahir Rahmanir Rahim */
/*Coder: Ahmad Faiyaz*/

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

# define FOR(i, a, b) for (int i=a; i<b; i++)
# define REP(i, a) FOR(i,0,a)

#define EPS 1e-11
#define inf ( 1LL << 31 ) - 1
#define LL long long

#define abs(x) (((x)< 0) ? (-(x)) : (x))
#define all(x) (x).begin(), (x).end()
#define ms(x, a) memset((x), (a), sizeof(x))

# define VI vector<int>
# define VS vector<string>
# define VC vector<char>

#define mp make_pair
#define pb push_back
#define sz(k) (int)(k).size()
#define FORIT(i,m) for(__typeof((m).begin()) i=(m).begin();i!=(m).end();i++)
#define pii pair<int,int>
using namespace std;
#define MAX 300005
struct node{
    int number,count;
};

int arr [MAX];
node tree [4*MAX];

vector <int> e [100005];

node combine(node l,node r){
    node ret;
    if(l.number == r.number){
        ret.number=l.number;
        ret.count= l.count+r.count;
    }
    else{
        if(l.count > r.count){
            ret.number= l.number;
            ret.count= l.count-r.count;
        }
        else{
            ret.number= r.number;
            ret.count= r.count-l.count;
        }
    }
    return ret;
}

node make (int val,int c){
    node ret;
    ret.count=c;
    ret.number=val;
    return ret;
}

void build(int node,int left,int right){
    if(left==right){
        tree[node]= make(arr[left],1);
        return;
    }

    int mid= (left+right)>>1;
    build(2*node,left,mid);
    build(2*node+1,mid+1,right);

    tree[node]= combine(tree[2*node],tree[2*node+1]);
    return;
}


node query(int node,int left,int right,int i,int j){
    if(left > j || right <i) return make(-1,-10000);
    if(left>= i && right<=j){
        return tree[node];
    }
    int mid= (left+right)/2;
    return combine(query(2*node,left,mid,i,j), query(2*node+1,mid+1,right,i,j));
}

int main(){
  //  freopen("in.txt","r",stdin);
  //  freopen("out.txt","w",stdout);
    int n,q,i,j;

    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
        e[arr[i]].pb(i);
    }
    build(1,0,n-1);
    scanf("%d",&q);
    while(q--){
        scanf("%d %d",&i,&j);
        node ret= query(1,0,n-1,i-1,j-1);
      //  cout<<ret.number<<" ";
        int cnt= upper_bound(all(e[ret.number]),j-1)-lower_bound(all(e[ret.number]),i-1);
        int elem= (j-i+1);

        if(2*cnt > elem){
            printf("yes %d\n",ret.number);
        }
        else{
            printf("no\n");
        }
    }

    return 0;
}

as far as i can see, i am doing same thing as told in the problem analysis!! but getting WA!! i have done checking with the official judge data, it seems that query function is not giving correct number for some range!! what to do?