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)解决了。。不知道我当时脑子怎么回事就没推出来
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5, mod = 1e9+7;
int a[maxn],n;
int p1[maxn],p2[maxn],p3[maxn],p11[maxn],p12[maxn],p31[maxn],p32[maxn];
void init(){
for(int i=1;i<=n;i++){
p1[i]=p1[i-1]^a[i];
p2[i]=p2[i-1]^p1[i];
p3[i]=p3[i-1]^p2[i];
}
for(int i=1;i<=n;i++){
if(i&1){
p11[i]=p11[i-1]^a[i],p12[i]=p12[i-1],p31[i]=p31[i-1]^p2[i],p32[i]=p32[i-1];
}
else{
p11[i]=p11[i-1],p12[i]=p12[i-1]^a[i],p31[i]=p31[i-1],p32[i]=p32[i-1]^p2[i];
}
}
}
int pp2(int x){
if(x<1)return 0;
return p2[x];
}
int pp3(int x){
if(x<1) return 0;
return p3[x];
}
int pp31(int x){
if(x<1) return 0;
return p31[x];
}
int pp32(int x){
if(x<1) return 0;
return p32[x];
}
int ww(int l,int r){
if(l==r) return a[l];
int res=0;
int t=(r-l+1)%4;
if(t==0){
return 0;
}
else if(t==1){
if(r&1){
return pp31(r)^pp31(l-3);
}
else{
return pp32(r)^pp32(l-3);
}
}
else if(t==2){
return pp3(l-3)^pp3(r);
}
else
{
if((r-1)&1){
return pp31(r-1)^pp31(l-2);
}
else{
return pp32(r-1)^pp32(l-2);
}
}
}
int main()
{
int t,l,r;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
init();
int q;
cin>>q;
while(q--){
scanf("%d%d",&l,&r);
printf("%d\n",ww(l,r));
}
}
return 0;
}