ARC092-D Two Sequences

using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
string s;
ll a[200001],b[200001];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=0;i<n;i++){
    cin>>b[i];
  }
  ll t=1;
  ll ans=0;
  for(int i=0;i<30;i++){
    if(i!=0)t*=2;
    vector<int> v1,v2;
    for(int j=0;j<n;j++){
      v1.push_back(a[j]%(2*t));
      v2.push_back(b[j]%(2*t));
    }
    sort(v2.begin(),v2.end());
    int res=0;
    for(int j=0;j<n;j++){
      int x=lower_bound(v2.begin(),v2.end(),t-v1[j])-v2.begin();
      int y=lower_bound(v2.begin(),v2.end(),2*t-v1[j])-v2.begin();
      int z=lower_bound(v2.begin(),v2.end(),3*t-v1[j])-v2.begin();
      res+=y-x;
      res+=n-z;
    }
    if(res&1){
      ans+=t;
    }
  }
  print(ans);
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

• 解説動画見て実装
• なんかむちゃくちゃ遅かった
• k- bit目が1か0かが周期的であることに気づけなかった
• xorを考えるときは各 bitごとに区切って考えるのが定石だそうです(ツイッターで誰かが言ってました)