题目描述

在加里敦中学的小明最近爱上了数学竞赛,很多数学竞赛的题目都是与序列的连续和相关的。所以对于一个序列,求出它们所有的连续和来说,小明觉得十分的简单。但今天小明遇到了一个序列和的难题,这个题目不仅要求你快速的求出所有的连续和,还要快速的求出这些连续和的异或值。小明很快的就求出了所有的连续和,但是小明想考考你,在不告诉连续和的情况下,让你快速的求出序列所有的连续和的异或值。

输入格式

第一行输入一个\(n\),表示这序列的数字个数。

第二行输入\(n\)个数字\(a_1,a_2,a_3\)…\(a_n\),代表这个序列。

\(0≤a_1,a_2,\)…\(,a_n,0≤a_1+a_2+\)…\(+a_n≤10^6\)。

输出格式

输出这个序列所有的连续和的异或值。

数据范围

对于\(20\%\)的数据,\(1≤n≤1000\)
对于\(100\%\)的数据,\(1≤n≤10^5\)


 

直接暴力\(O(n^2)\),可以获得\(20\)分

考虑按位枚举,题目保证了\(0≤a_1+a_2+\)…\(+a_n≤10^6\)

那么显然,我们最多只需要枚举\(20\)位

对于枚举的每一位,我们希望快速地算出有多少和在这一位上有贡献\(1\)

显然,一个和我们可以通过前缀和的预处理,\(\sum_{i=l}^r=sum[r]-sum[l-1]\)

当我们知道了当前\(x\),\(sum[x]\)的第\(i\)位为\(1\)的时候,我们要知道以这一位为结束区间有多少贡献为\(1\)的

显然只有两种情况,当\(sum[y](y<x)\)的第\(i\)位也是\(1\)的时候,\(y\)的后面几位必须比\(x\)大才可以使得\(x\)的前面退位,使得区间\(\sum_{i=y-1}^x\)产生贡献

当\(sum[y](y<x)\)的第\(i\)位也是\(0\)的时候,\(y\)的后面几位必须比\(x\)小才可以保住\(x\)的贡献

而满足这样的两个条件,我们可以用树状数组来简单地维护一下

\(x\)的第\(i\)位为\(0\)的时候,一样的分析一下就好了

还有一个细节就是,计算贡献的时候,可能答案会超过int,那就让他自然溢出好了,就是最后计算的时候注意取模的正负即可

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注