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

· · 题解

分析

要求的是异或和等于 0 的区间的个数

暴力枚举左右端点显然会 T 飞

考虑将问题转化一下

设 sum 数组为异或的前缀和

如果有 a_l⊗a_{l+1}⊗…a_{r-1}⊗a_r=0

那么就有 sum[l-1]=sum[r]

对于一个前缀和 x，如果一共有 cnt 个前缀和和其相等

那么合法的方案数就是 \frac{cnt(cnt+1)}{2}

把前缀和扔进哈希表里，记录一下个数即可

考虑修改操作

如果把 a[p] 和 a[p+1] 都异或上 x

那么根据异或的性质 x⊗x=0

改变的只是 sum[p]，其它的都不变，相当于单点修改

在哈希表里随便改一下即可

时间复杂度 O(n)

目前是最优解

代码

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({ register int x = 0; register char c = gc(); while(!isdigit(c)) c = gc(); while(isdigit(c)) x = x * 10 + (c & 15), c = gc(); x; })
char buf[1 << 20], *p1, *p2;
const int maxn=1e6+5;
const int mod=1e6+3;
int a[maxn],n,m;
long long ans1,ans2,ans3,ans4=0x3f3f3f3f3f3f3f3f,ans;
int sum[maxn],h[maxn],tot=1;
struct asd{
    int val,nxt,cnt;
}b[maxn*8];
long long js(int num){
    return 1LL*(num-1)*num/2;
}
void ad(int num,int val){
    rg int now=num%mod;
    for(rg int i=h[now];i!=-1;i=b[i].nxt){
        if(num==b[i].val){
            ans-=js(b[i].cnt);
            b[i].cnt+=val;
            ans+=js(b[i].cnt);
            return;
        }
    }
    b[tot].nxt=h[now];
    b[tot].val=num;
    b[tot].cnt=1;
    h[now]=tot++;
}
int main(){
    memset(h,-1,sizeof(h));
    n=read(),m=read();
    for(rg int i=1;i<=n;i++){
        a[i]=read();
    }
    ad(0,1);
    for(rg int i=1;i<=n;i++){
        sum[i]=sum[i-1]^a[i];
        ad(sum[i],1);
    }
    rg int aa,bb;
    for(rg int i=1;i<=m;i++){
        aa=read(),bb=read();
        ad(sum[aa],-1);
        sum[aa]^=bb;
        ad(sum[aa],1);
        ans1^=ans;
        if(ans&1) ans2++;
        ans3=max(ans,ans3);
        ans4=min(ans,ans4);
    }
    printf("%lld\n%lld\n%lld\n%lld\n",ans1,ans2,ans3,ans4);
    return 0;
}