over 4 years ago

给定一个n个数的序列,每个数均不超过c. 然后m次查询,每次查询l到r内出现了偶数次的数的数目。 (n,m,c <= 10^5)

恩,一眼就看到是分块。

将n个数分成根号n块,统计每两个块之间有多少个数出现了偶数次。

查询的时候块内O(1)出借,块边缘暴力,对于数i,二分出块内i出现的次数Ci,与块边缘的出现次数Di更新解

这个算法常数感人.

应该存在更优的解法: 比如按位置建主席树, 统计某个值域的出现次数, 查询的时候相减就好了. (纯属嘴巴)

← BZOJ 3218 A+B PROBLEM CF #257 .Div 1 →
 
comments powered by Disqus