Skip to content

Instantly share code, notes, and snippets.

@ar-pa
Created January 12, 2017 08:37
Show Gist options
  • Save ar-pa/1ef83ee2ecd4293d1652facd496a78d8 to your computer and use it in GitHub Desktop.
Save ar-pa/1ef83ee2ecd4293d1652facd496a78d8 to your computer and use it in GitHub Desktop.
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment