题解：P3760 [TJOI2017] 异或和

· · 题解

题目传送门。

思路

问题就是求所有区间和的异或和，这种统计区间贡献问题不难想到分治，假设当前的分治区间为 [l,r]，区间中点为 mid，对 [l,mid] 的 a_i 做一遍后缀和得到 sml，对 [mid+1,r] 的 a_i 做一遍前缀和得到 smr，那么问题就转换成了求 \oplus_{i\in [l,mid]} \oplus_{j\in[mid+1,r]}(sml_i+smr_j)。

首先容易想到按位拆贡献，只需对每个位 i 求出有多少个 sml_j+smr_k(j\le k) 使得其和的第 i 位上为 1。

不妨舍去 i 位以后的位，那么 sml_j+smr_k 的范围就在 [0,2^i),[2^i,2^{i+1}),[2^{i+1},2^{i+1}+2^i),[2^{i+1}+2^i,2^{i+2}) 其中之一，显然只有第 2,4 个区间有贡献，剩下的问题就是对于一个已知的 u 如何快速求出有多少个 j,k(j\le k) 使得 sml_j+smr_k\ge u 了，这是个经典的问题，排序双指针即可。

归并排序即可做到 \mathcal O(n\log V)。

总时间复杂度就是 \mathcal O(n\log n\log V)。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=1e5+6;
int n;
int a[Maxn];
int b[Maxn],c[Maxn];
int sm[Maxn];

inline void mergesort(int t[],int l,int r,int i){
    int tot1=0,tot2=0;
    for(int j=l;j<=r;j++) 
        if(t[j]>>(i+1)&1) b[++tot1]=t[j]-(1<<(i+1)); 
        else c[++tot2]=t[j];
    merge(b+1,b+tot1+1,c+1,c+tot2+1,t+l);
}
inline int calc(int u,int L,int mid,int R){
    int r=R+1;int ret=0;
    for(int l=L;l<=mid;l++){
        while(sm[r-1]+sm[l]>=u and r-1>mid) --r;
        ret=ret^((R-r+1)&1);
    }
    return ret&1;
}

int solve(int l,int r){
    if(l>r) return 0;
    if(l==r) return a[l];
    int mid=l+r>>1,ret=0;
    sm[mid]=a[mid],sm[mid+1]=a[mid+1];
    for(int i=mid-1;i>=l;i--) sm[i]=sm[i+1]+a[i];
    for(int i=mid+2;i<=r;i++) sm[i]=sm[i-1]+a[i];

    sort(sm+l,sm+mid+1),sort(sm+mid+1,sm+r);
    for(int i=20;~i;i--){
        mergesort(sm,l,mid,i);
        mergesort(sm,mid+1,r,i);
        int u=1<<i;
        if((calc(u,l,mid,r)-calc(u*2,l,mid,r)+calc(u*3,l,mid,r))&1) ret^=(1<<i);
    }

    return solve(l,mid)^solve(mid+1,r)^ret;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    printf("%d",solve(1,n));

    return 0;
}