fork download
  1. #include <bits/stdc++.h>
  2. #include <ext/numeric>
  3. #include <ext/hash_map>
  4. using namespace std;
  5. using namespace __gnu_cxx;
  6.  
  7. #define oo 1e9
  8. #define OO 1e18
  9. #define EPS 1e-7
  10. #define f first
  11. #define s second
  12. #define pi acos(-1.0)
  13. #define ll long long
  14. #define ld long double
  15. #define ull unsigned long long
  16. #define sz(x) (int)x.size()
  17. #define all(x) x.begin(),x.end()
  18. #define rall(x) x.rbegin(),x.rend()
  19. #define popCnt(x) __builtin_popcount(x)
  20.  
  21. int n,c,m;
  22. int arr[300300];
  23. map<int,vector<int> > idxS;
  24. int cntBit[18][300300];
  25.  
  26. int getCnt(int v,int l,int r){
  27. return (upper_bound(all(idxS[v]),r)-idxS[v].begin())
  28. -(lower_bound(all(idxS[v]),l)-idxS[v].begin());
  29. }
  30.  
  31. int main() {
  32. #ifndef ONLINE_JUDGE
  33. freopen("input.txt", "rt", stdin);
  34. //freopen("output.txt", "wt", stdout);
  35. #endif
  36. scanf("%d%d",&n,&c);
  37. for(int i=1;i<=n;i++){
  38. scanf("%d",&arr[i]);
  39. idxS[arr[i]].push_back(i);
  40. }
  41. for(int i=0;i<17;i++)
  42. for(int j=1;j<=n;j++)
  43. cntBit[i][j]=cntBit[i][j-1]+((arr[j]&(1<<i))!=0);
  44. scanf("%d",&m);
  45. while(m--){
  46. int l,r;
  47. scanf("%d%d",&l,&r);
  48. int siz=(r-l+1)/2,cur=0;
  49. for(int i=0;i<17;i++)
  50. if(cntBit[i][r]-cntBit[i][l-1]>siz)cur|=(1<<i);
  51. int cnt=getCnt(cur,l,r);
  52. if(cnt<=siz)printf("no\n");
  53. else printf("yes %d\n",cur);
  54. }
  55. }
  56.  
Success #stdin #stdout 0s 25752KB
stdin
10 3
1 2 1 2 1 2 3 2 3 3
8
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10
stdout
no
yes 1
no
yes 1
no
yes 2
no
yes 3