- 给定 $n$ 个数字 $a_1,a_2,\cdots,a_n$。
- $m$ 次询问，每次询问给定 $x$，求 $\oplus_{i=1}^n (a_i+x)$ 的值。
- 强制在线。
- $1\leq n,m\leq 2.5\times 10^5,0\leq a_i,x\lt 2^{60}$。
sol
-
由于每个 $a_i$ 加的都是 $x$，所以向第 $w$ 位进位的一定是后 $w-1$ 位 $a_i$ 最大的若干个数。
-
从低到高考虑每一位。讨论 $x$ 当前这一位是 $0$ 还是 $1$。
- 如果当前位为 0：
- $a_i+x$ 当前位为 $1$ 的数量：进位为 $0$ 且 $x$ 当前位为 $1$ 的数量 + 进位为 $1$ 且 $x$ 当前位为 $0$ 的数量；
- $a_i+x$ 向前进位的数量：进位为 $1$ 且 $x$ 当前位为 $1$ 的数量。
- 如果当前位为 1：
- $a_i+x$ 当前位为 $1$ 的数量：进位为 $1$ 且 $x$ 当前位为 $1$ 的数量 + 进位为 $0$ 且 $x$ 当前位为 $0$ 的数量；
-
$a_i+x$ 没向前进位的数量：进位为 $0$ 且 $x$ 当前位为 $0$ 的数量，向前进位的数量用 $n$ 减去即可。
-
记 $sum[0/1][w][i]$ 为考虑后 $w-1$ 位有 $i$ 个数进位，第 $i$ 位没进位/进位的数的个数。
- 可以用基数排序优化每次的排序。
```cpp
include
using namespace std;
typedef long long ll;
const ll INF=1ll<<60;
int n,m,t,sum[2][64][260000],tmp[2][260000],p[260000];
ll ans,v,a[260000];
int main(){
scanf("%d%d%d",&n,&m,&t);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]),p[i]=i;
for (int w=0;w<62;w++){
tmp[0][0]=0; tmp[1][0]=0;
for (int i=1;i<=n;i++){
int x=(a[p[i]]>>w)&1; tmp[x][++tmp[x][0]]=p[i];
sum[0][w][i]=tmp[0][0]; sum[1][w][i]=tmp[1][0];
}
for (int i=1;i<=tmp[0][0];i++) p[i]=tmp[0][i];
for (int i=1;i<=tmp[1][0];i++) p[i+tmp[0][0]]=tmp[1][i];
}
for (int i=1;i<=m;i++){
scanf("%lld",&v); v^=(t*(ans>>20));
int x=0; ans=0;
for (int w=0;w<62;w++)
if ((v>>w)&1){
ans^=(((sum[1][w][n]-sum[1][w][n-x])+sum[0][w][n-x])&1ll)<<w;
x=n-sum[0][w][n-x];
} else{
ans^=(((sum[0][w][n]-sum[0][w][n-x])+sum[1][w][n-x])&1ll)<<w;
x=sum[1][w][n]-sum[1][w][n-x];
}
printf("%lld\n",ans);
}
return 0;
}
```