solution for http://www.spoj.com/problems/PATULJCI/

PATULJCI.cpp

// God & me
// Together :)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 17, undef = maxn - 1;
int n, m, c;
vector<int> vec[maxn];
struct node{
    int l, r, ans;
    node(){  l = r = ans = undef;  }
}  iman[maxn << 1];
int occ(int x, int l, int r){
    return lower_bound(vec[x].begin(), vec[x].end(), r) - lower_bound(vec[x].begin(), vec[x].end(), l);
}
node operator +(node a, node b){
    if(a.l == undef)  return b;
    if(b.l == undef)  return a;
    node ans;
    ans.l = a.l, ans.r = b.r;
    for(auto candidate : {a.ans, b.ans})
	if(occ(candidate, ans.l, ans.r) > (ans.r - ans.l) / 2)
	    ans.ans = candidate;
    return ans;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> c;
    for(int i = 0; i < n; i++){
	cin >> iman[i + n].ans;
	iman[i + n].l = i, iman[i + n].r = i + 1;
	vec[ iman[i + n].ans ].push_back(i);
    }
    for(int i = n - 1; i > 0; i--)
	iman[i] = iman[i << 1] + iman[i << 1 | 1];
    int q;  cin >> q;
    for(int l, r; q--; ){
	cin >> l >> r, l--;
	node L, R;
	for(l += n, r += n; l < r; l >>= 1, r >>= 1){
	    if(l & 1)  L = L + iman[l++];
	    if(r & 1)  R = iman[--r] + R;
	}
	node ans = L + R;
	if(ans.ans != undef)
	    cout << "yes " << ans.ans << '\n';
	else
	    cout << "no\n";
    }
    return 0;
}