题解 P7096 【[yLOI2020] 泸沽寻梦】

题目传送门

更不好的阅读体验

第一次写题解写得稍微详细点

题意简述

给定长度为 n 的非负整数数列 a_i 与 m 次操作，每次操作给定 p 和 x，将相邻两个数 a_p 和 a_{p+1} 按位异或上 x，要求在每次操作后求出异或和为 0 的子区间个数。

题目分析

为了方便这里记 a[l...r] 的异或和为 S(l,r) 。

首先，需要知道异或有结合律与交换律。

带修有些麻烦，先来考虑没有修改时如何计算答案。

最暴力的当然是枚举每个子区间并 O(n) 判断，总共 O(n^3)，带修就是 O(n^4)，期望得分 10 pts。

S(1,l-1) \oplus S(l,r)=S(1,r) S(1,l-1) \oplus S(l,r) \oplus S(1,l-1)=S(1,r) \oplus S(1,l-1) S(l,r)=S(1,r) \oplus S(1,l-1)

用前缀和优化一下，判断就可以 O(1) 了，总共 O(n^2)，带修 O(n^3)，期望得分 20pts。

由上面那个式子可以发现 S(l,r)=0 当且仅当 S(1,l-1)=S(1,r)。

所以如果用 cnt_k 表示所有 S(1,i) 中值为 k 的个数，那么答案就是

ans= \sum\limits_i \frac{1}{2}cnt_i(cnt_i-1)

考虑用 map 存，当然可以在统计 cnt_i 时顺便更新答案

\Delta ans=\frac{1}{2}[cnt_i(cnt_i+1)-cnt_i(cnt_i-1)]=cnt_i

总共 O(n)，带修 O(n^2)，期望得分 40pts。

单次计算已经很优了，来考虑带修。

然后会发现每次修改只会改变 S(1,p)，因为对于后面的前缀异或和，每个都异或上了两次 x，也就是不变。

答案维护和上面一样。

然而由于 map 常数太大了，貌似要用 unordered_map 才能卡过去……

请注意，a_i,x \leq Y 不能说明 a_i \oplus x \leq Y。

别忘了long long

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;

int n,m;
long long s[N];
long long ans;
long long ansxor,ansj,ansmax=0,ansmin=1e18;
unordered_map <long long,int> mp;

int main(){
    scanf("%d%d",&n,&m);
    mp[0]++;
    for(int i=1;i<=n;i++){
        int a;
        scanf("%d",&a);
        s[i]=s[i-1]^a;//前缀异或和 
        ans+=mp[s[i]],mp[s[i]]++;
    }

    for(int i=1;i<=m;i++){
        int p,x;
        scanf("%d%d",&p,&x);
        ans-=mp[s[p]]-1,mp[s[p]]--;
        ans+=mp[s[p]^x],mp[s[p]^x]++;
        s[p]^=x;//将s[p]变为s[p]^x，同时更新答案 

        ansxor^=ans;
        if(ans & 1ll) ansj++;
        ansmax=max(ansmax,ans);
        ansmin=min(ansmin,ans); 
    }
    printf("%lld\n%lld\n%lld\n%lld\n",ansxor,ansj,ansmax,ansmin);
}