code的作法可以參考這篇。
也有一個直覺的作法是利用持久化權值線段樹,可以參考這篇。
#include<bits/stdc++.h> using namespace std; const int maxn=1000000; vector<int> show[maxn]; int n,m,a[maxn],pre[20][maxn]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",a+i); for(int j=0;(1<<j)<=n;j++) pre[j][i]=pre[j][i-1]+(a[i]&(1<<j)?1:0); show[a[i]].push_back(i); } int L,R; while(m--) { scanf("%d%d",&L,&R); int tar=(R-L+1)/2+1,ans=0; for(int i=0;(1<<i)<=n;i++) { int cnt=pre[i][R]-pre[i][L-1]; if(cnt>=tar) ans|=(1<<i); } int tmpR=upper_bound(show[ans].begin(),show[ans].end(),R)-show[ans].begin(); int tmpL=lower_bound(show[ans].begin(),show[ans].end(),L)-show[ans].begin(); if(tmpR-tmpL>=tar) printf("%d\n",ans); else printf("0\n"); } }
沒有留言:
張貼留言