[每日一题] [NC14414] 小AA的数列

题目大意：
给定一个int数组，求所有长度为偶数的连续区间，且长度在[L,R]区间内，xor的总和。

https://ac.nowcoder.com/acm/problem/14414

很明显，可以不妨只对一个数位进行计算。如果我们知道倒数第五位，xor在这一位为1的符合要求的区间个数为10，那么我们知道倒数第五位xor对于总和的贡献是10*(1<<4)=160，等等。

对于一个数位，问题变成了，给定一个binary array，有多少个长度为偶数，在[L, R]区间内，且有奇数个1的区间个数。显然可以拆分成(0, R]和(0, L-1]的差简化问题。于是问题化为了，给定一个0/1数组，有多少个长度不超过R的偶数长区间总和为奇数。如果没有总和为奇数，那么终点为i的这样的区间个数不难用数学表达出来，如果i超过R，则区间个数为R/2左右，否则为i/2左右。所以只需要计算多少个长度不超过R的偶数长区间总和为偶数。

我们考虑前缀和数组p，那么就是问有多少对p[i], p[j], s.t. i < j <= i + R，且i、j同奇偶，且p[i]和p[j]同奇偶。我们对于前缀和数组的奇偶以及下标的奇偶分成2x2=4组，比如所有i为偶且p[i]为偶分为一组。那么就需要知道每组有多少个下标满足i<j<=i+R.

问题简化为给定一个排好序的数组，有多少个其中的pair，差距不超过R。那么用slow fast pointers就可以了。代码如下。

doit3是不用slow fast pointer的实现应该会TLE，最后进行了doit2的优化。

#include <bits/stdc++.h>
#define MOD 1000000007LL

ll doit3(int N, int R, VI& nums, int d) {
  VI binary;
  REP(i,N){
    binary.PB((nums[i]&(1<<d))!=0);
  }
  printf("N=%d,R=%d,d=%d\n",N,R,d);
  println(binary);
  // number of even length interval <= R
  // which contains odd number of 1s.
  // At each prefix sum p[i], how many j with same parity, s.t.
  // j >= i - R.
  // Consider p[i] that is odd and i is odd, p[i] that is even and i is even, etc.
  // Need to compute how many of them have gap <= R.
  VVI gaps(4);
  gaps[0*2+1].PB(-1);
  int parity = 0;
  REP(i,N){
    parity+=binary[i];
    parity%=2;
    gaps[parity*2+(i%2)].PB(i);
  }
  ll ans = 0;
  REP(i,4){
    FOR(j,0,sz(gaps[i])-1){
      FOR(k,j+1,sz(gaps[i])-1){
        if(gaps[i][k]-gaps[i][j]<=R){
          ++ans;
        }
      }
    }
  }
  ll tot = 0;
  REP(i,N){
    int hi = i - 2;
    int lo = std::max(-1, i - R);
    if ((i-lo)%2)++lo;
    if(hi>=lo){
      tot+=(hi-lo)/2+1;
    }
  }
  ans= tot-ans;
  printlong(ans);
  return ans;
}

ll getcount(VI& gaps, int R) {
  // How many elements in gaps have distance <= R.
  int n = sz(gaps);
  int j = 0;
  ll ans = 0;
  REP(i,n){
    while(gaps[j]<gaps[i]-R){
      ++j;
    }
    ans+=ll(i-j);
  }
  return ans;
}

ll doit2(int N, int R, VI& nums, int d) {
  VI binary;
  REP(i,N){
    binary.PB((nums[i]&(1<<d))!=0);
  }
  // number of even length interval <= R
  // which contains odd number of 1s.
  // At each prefix sum p[i], how many j with same parity, s.t.
  // j >= i - R.
  // Consider p[i] that is odd and i is odd, p[i] that is even and i is even, etc.
  // Need to compute how many of them have gap <= R.
  VVI gaps(4);
  gaps[0*2+1].PB(-1);
  int parity = 0;
  REP(i,N){
    parity+=binary[i];
    parity%=2;
    gaps[parity*2+(i%2)].PB(i);
  }
  ll ans = 0;
  REP(i,4){
    ans += getcount(gaps[i],R);
  }
  ll tot = 0;
  REP(i,N){
    int hi = i - 2;
    int lo = std::max(-1, i - R);
    if ((i-lo)%2)++lo;
    if(hi>=lo){
      tot+=(hi-lo)/2+1;
    }
  }
  ans= tot-ans;
  return ans;
}

ll doit(int N, int R, VI& nums) {
  // Sum of xor sum for intervals of even length <= R.
  ll ans = 0;
  for (int d = 0; d <= 30; ++d) {
    ll mycount = doit2(N, R, nums, d);
    mycount %= MOD;
    ll mod = (1LL<<d)%MOD;
    ans += (mod * mycount)%MOD;
    ans%=MOD;
  }
  return ans;
}

ll doit(int N, int L, int R, VI& nums) {
  return (doit(N,R,nums) + (MOD - doit(N,L-1,nums))%MOD)%MOD;
}

int main(int argc, char* argv[]) {
  /* Do not use for codejam. */
  /* ios_base::sync_with_stdio(false); cin.tie(NULL); */
  read3int(N,L,R);
  readvi(nums,N);
  printlong(doit(N,L,R,nums));
  return 0;
}