2019 ICPC南昌邀请赛网络赛 K MORE XOR
(⊙﹏⊙)不知道为什么比赛时候这个题和D题死推不出来，比赛完了5分钟ac，我大概脑子坏掉了。真的是超超超超级简单的一个题，但是我光顾着用数学公式推了所以推出来结果巨复杂(⊙﹏⊙)服了自己了。
题解：先说怎么求g(l,r): 首先f(l,r)很好求，利用异或的性质，预处理出来前缀异或和就可以了。设预处理出来p1[x]表示从a[1]到a[x]的异或和，那么很容易得到\[f(l,r)=p1[l-1]\oplus p2[r] \], 那么可以由g的定义就可以知道 \[ g(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} f(i,j) =\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} p1[i-1]\oplus p1[j] \];当然这个东西还是很复杂的，我们想办法把他复杂度搞到O(1)：考虑每个p1[x]出现的次数，列个表可以发现，在这个求和式中出现的所有下标，从l-1变化到r, 而每个下标出现的次数都是一样的，这个次数等于 r-l+1 ，那么就可以得出结论，如果r-l+1为偶数，则g(l,r)应为0，否则应为\[ \sum_{i=l-1}^{r} p1[i] \]，注意到这个式子又可以用p1的前缀和来O(1)计算，所以又可以提前求出来p1的前缀和p2，这样的话g(l,r)就可以表示为
\[g(l,r)=\begin{cases}
0& \text{(r-l+1) is odd}\\
p2[l-2]\oplus p2[r]& \text{else }
\end{cases}\]
有了g(l,r)再来考虑w(l,r)，\[w(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} g(i,j) \],就跟g的表达式很像，但是这里不能直接再套用g关于p1的公式，因为g里面有很多的0是跟p2无关的，换句话说这些0并不是由p2[l-2]^p2[r]求出来的，所以要分类讨论。分析方法跟g是类似的，列一个表观察每个p2出现的规律，可以发现，这个规律是4个一循环的结构，设\[t=（r-l+1)\mod 4\]; 则当t==0时，所有的p2下标出现次数均为偶数次，也就是结果一定为0，t==2时，所有的p2下标出现次数均为奇数，这样的话即等于\[\sum_{i=l-1}^{r} p2[i] \]，这个式子说明我们可以再用一个p2的前缀和p3来O(1)计算这个结果。这是比较简单的两种情况，另外两种是t==1和t==3，这两种一种是奇数项的出现次数为奇数偶数项为偶数，另一种是奇数项出现次数为偶数而偶数项出现次数为奇数，这意味着可以用一个分奇偶的前缀和来O(1)求得这个式子只不过仍需要分类讨论一次。。若令p31[i]和p32[i]分别表示p2的奇偶前缀和，t=(r-l+1)%4, 则w(l,r)的表达式为
\[w(l,r)=
\begin{cases}
0& \text{t=0}\\
p31[r]\oplus p31[l-3]& \text{t=1 and r is odd}\\
p32[r]\oplus p32[l-3]& \text{t=1 and r is even}\\
p3[l-3]\oplus p3[r]& \text{t=2}\\
p32[r-1]\oplus p32[l-2]& \text{t=3 and r is odd}\\
p31[r]\oplus p31[l-3]& \text{t=3 and r is even}
\end{cases}
\]
这样的话整个问题就可以O(1)解决了。。不知道我当时脑子怎么回事就没推出来
继续阅读“[比赛补题][×] 2019 ICPC南昌邀请赛网络赛 K MORE XOR”
