题解：AT_abc365_e [ABC365E] Xor Sigma Problem

xwh_hh · 2024-08-10 11:30:19 · 题解

奇迹般地独立过了 E 题，发篇题解纪念一下。
注：本文中均使用小写字母作变量名，请注意与题目的微小区别。
不难想到维护前缀异或和（此处记 b_i=a_1\oplus a_2\oplus\cdots\oplus a_i，特殊的，b_0=0），则所求的式子即为 \sum_{i=0}^{n-2} \sum_{j=i+2}^nb_i\oplus b_j=(\sum_{i=0}^{n-1} \sum_{j=i+1}^nb_i\oplus b_j)-(\sum_{i=1}^na_i)，后面一部分明显可以 O(n) 求出，问题转化为求 \sum_{i=0}^{n-1} \sum_{j=i+1}^nb_i\oplus b_j 的值。

直接暴力求解是 O(n^2) 的，无法通过，我们考虑快速求出 \sum_{i=0}^{x-1}b_i\oplus b_x。

因为这是位运算，不难想到按位考虑。记 g_{i,j} 表示当前考虑范围内的数中满足二进制表示中第 i 位为 j 的数的个数（记最低位为第 0 位），每次更新 g 数组时只需 O(\log a_{\max}) 的复杂度，统计答案单次也是 O(\log a_{\max})，总时间复杂度 O(n\log a_{\max})，可以通过本题。
代码如下（比较通俗易懂）：

#include<bits/stdc++.h>
using namespace std;
inline long long read(){
    long long ans=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-f;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        ans=(ans<<3)+(ans<<1)+c-48;
        c=getchar();
    }
    return ans*f;
} 
void write(long long x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x<10) putchar(x+48);
    else{
        write(x/10);
        putchar(x%10+48);
    }
}
long long n;
long long a[200005],b[200005];
long long g[35][2];
long long ans;
signed main(){
    n=read();
    for(long long i=1;i<=n;i++){
        a[i]=read();
        b[i]=a[i]^b[i-1];
    }
    for(long long i=0;i<=28;i++) g[i][0]++;//将b[0]加进去 
    for(long long i=1;i<=n;i++){
        for(long long j=0;j<=28;j++){
            ans+=g[j][bool((b[i])&(1<<j))^1]*(1<<j);//按位统计答案 
        }
        for(long long j=0;j<=28;j++){
            g[j][bool((b[i])&(1<<j))]++;//按位更新g数组 
        }
    }
    for(long long i=1;i<=n;i++) ans-=a[i];//除去长度为1的区间 
    write(ans);
    return 0;
}

小插曲：赛时我把 a_i 的上限看成了 10^{18}，害得我开了 __int128，赛后才发现 long long 就够了。