lkMiles

退役oier

BZOJ 4017 小Q的无敌异或

这道题是邱老师讲过的一道数据结构的卡常题(至少我觉得,嗯没错我就被卡掉了),题意是求所有区间的和的异或以及异或和的和。

题解:
1.对于异或的和,假设我们f(i)表示异或前缀,那么一个区间的异或值为f(R)^f(L-1),那我们先处理出所有的前缀异或值
到了一点pos,发现我们要统计的那些右端点为pos的值为sigma(i) f(pos)^f(i) (0<=i<pos),难道我们要暴力吗?我们发现不能这样。
首先我们可以巧妙地发现,如果f(pos)的第k位是1,那么意味着之前所有第k位是1的会减掉2^k,不是1的会加上2^k,统计答案,然后插入f(pos)到数组里,这样统计答案是O(n*logn)
2.s[i]表示i的前缀和,对于和的异或,考虑如果对k这一位是1那么就意味着所有的(s[j]-s[i])%(2^(k+1))>=2^k的个数为奇数,那么枚举一个i,然后树状数组(我写的动态建树线段树然后被卡常了)处理j的答案即可,这个的时间复杂度是O(n*logn^2)

这道题好迷阿,拿到数据手跑每个点都是1.2s出答案,心塞。那就不粘code了免得丢人

评论
©lkMiles
Powered by LOFTER