题目大意:
给定一个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; }