牛客2020寒假训练营4-D

牛客2020寒假训练营4-D

七月 15, 2020

子段异或

题意
输入一个数列a，你需要输出其中异或值为0的不同子段的数量。一个子段 [l,r] (
1≤l≤r≤n)的异或值为al⊕al+1⊕al+2⊕…⊕ar，其中⊕符号代表异或运算。

题解

如果[l,r]是合法的子段，说明前缀和中xorsum[r]^xorsum[l-1] = 0, xorsum[l-1] = xorsum[r]。求出异或前缀和，然后使用map计数每一个数字有多少个前缀和等于那个数字即可。

如果题目改为输出其中异或值为a的不同字段的数量
那么xorsum[r]^xorsum[l-1]=a
那么对于一个xorsum[r] 要求前面又几个xorsum[l]=a^xorsum[r]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll data[(int)2e5+5];
ll xorsum[(int)2e5+5];
map<ll,int>cnt;
int main(){
    int n;cin>>n;cnt[0]++;
    ll ans=0;
    for(int i=1;i<=n;i++){
        cin>>data[i];
        xorsum[i]=xorsum[i-1]^data[i];
        if(cnt.count(xorsum[i])){
            ans+=cnt[xorsum[i]];
        }
        cnt[xorsum[i]]++;
    }
    cout<<ans<<endl;
}