codeforces #340 div 2 E XOR and Favorite Number

http://codeforces.com/contest/617/problem/E

题意:给出n个数,m个查询,每个查询给定l,r,问在区间【l,r】内,有多少对i,j,满足i^(i+1)^(i+2)^…^j的值为给定的常数k.

思路:学了莫队算法以后。。。这题果然是莫队的一眼题。

入手点是,知道异或也像加一样有前缀和性质。如果我们处理一个按照异或规则的前缀和数组sum[i]=sum[i-1]^a[i],那么i到j的异或和就是sum[i-1]^sum[j]  (x^x==0,因此a[1]到a[i-1]的异或和被去掉了)

因此我们要找的就是区间内有多对i,j满足sum[i-1]^sum[j]==k,也就是sum[i-1]==k^sum[j]这和hdu 5213 a=k-b有如此类似的形式,做法也是类似的。

由于对于每个j,找的是i-1,在处理的时候记得将区间左端点-1,

最重要的一点是,莫队的添加和删除操作最好分开写,至少根据d的正负写个if else,因为顺序不一定相同。

最后一个注意的是,可能会爆int ,所以要用long long

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz