异或操作,直接考虑如何构造x对应二进制的每一位能使 x ^ a[i] 最大。
那么x的第i位为0时当前位的贡献为[l,r]内a[j]的第i位为1的个数*2^i。所以我们只需要预处理出a[i]对应二进制为的前缀1的个数,然后每次询问枚举每一位分类讨论就好了
#include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define SZ(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() #define rep(i,a,b) for(ll i=(a);i<=(b);i++) #define per(i,a,b) for(ll i=(a);i>=(b);i--) using namespace std; typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii; const int mod = 1e9 + 7; const int maxn = 1e6 + 4; const int N = 1000 + 5; ll qpow(ll x,ll y){ll ans=1;x%=mod;assert(y>=0);while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;} //ctrl + h ctrl + shift + t //ctrl + shift + d/k //alt + shift + 1/2/3/4 int n,m,q,l,r,a[maxn],cnt[maxn][33]; int main() { //freopen("input.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { for(int j=0;j<=31;j++) { cnt[i][j]=cnt[i-1][j]+a[i]%2; a[i]/=2; } } scanf("%d",&q); while(q--) { scanf("%d%d",&l,&r); ll ans=0; for(int i=30;i>=0;i--) { int z=cnt[r][i]-cnt[l-1][i],m=r-l+1; if(m%2==0) { if(z>=m/2) ans=ans*2; else ans=ans*2+1; } else { if(z>m/2) ans=ans*2; else ans=ans*2+1; } } printf("%lld\n",ans); } return 0; }