原题:洛谷P9533
一道性质题
不难发现,区间翻转操作是没有用的(虽然比赛的时候想了好久www)
首先,区间翻转要想对答案有贡献,一定是下边这种情况:
三个连续的区间:\(A~|~B~|~C\)
满足:\(B \oplus C=0,A \oplus C=0\)。
将 \(B∪C\) 这个灵异区间进行翻转,使 \(A\) 和 \(C\) 合并到一起,会增加一个灵异区间 \(A∪C\)。
但是,如果 \(B \oplus C=0,A \oplus C=0\) ,那么 也有\(A \oplus B=0\)。
因为:若 \(B \oplus C=0,A \oplus C=0\),则 \(\bigoplus B=\bigoplus C,\bigoplus A=\bigoplus C\)。
所以 \(\bigoplus A=\bigoplus B\),即 \(A \oplus B=0\)。
所以翻转前 \(A∪B\) 也是灵异区间,而反转后这个灵异区间就没有了。
所以区间翻转实际上是没用的。
然后就好写了,统计原数组的灵异区间即可
原理很简单:维护一个异或前缀和 \(sum\),并用 \(cnt_i\) 记录前缀和为 \(i\) 出现的次数。
比如如果 \(sum_i=sum_j=x\),则区间 \([i+1,j]\) 的异或和为0,即为灵异区间。
且 若也有 \(sum_k=x(i<j<k)\),则区间 \([i+1,k]\) 中共有 \(2+1=3\) 个灵异区间(\([i+1,j],[j+1,k],[i+1,k]\))。
即若前缀和 \(x\) 出现了 \(m\) 次,则灵异区间有 \(1+2+3+...+m=m(m-1)/2\) 个
我们再用 \(a\) 数组记录每种不同的前缀和,遍历 \(a\) 数组计算并统计灵异区间数量即可。
还要特殊处理一下 \(0\),很简单,\(sum\) 的初值是 \(0\),我们把这个 \(0\) 也计入计算即可
n=read();
cnt[0]=1;a[++tot]=0;
while(n--)
{
sum^=read();
if(!m[sum]) a[++tot]=sum;
cnt[sum]++;
}
for(reg int i=1;i<=tot;i=-~i) ans+=cnt[a[i]]*(cnt[a[i]]-1)/2;
printf("%lld",ans);
标签:洛谷,题解,sum,bigoplus,区间,oplus,翻转,灵异
From: https://www.cnblogs.com/sorato/p/17627729.html