Description
有一个长度为 \(n(1\le n \le 10^6)\) 的序列 \(a(1\le a_i \le 10^6)\)，给出 \(Q(1\le Q \le 10^6)\) 组询问，询问区间 \([l, r]\) 内是否每个元素都出现了偶数次。
Solution
By zty
先来介绍介绍我的同学 zty 的做法。
他的做法是：首先记录一个系数数组 \(x_i\)，如果 \(a_i\) 在序列里面出现了奇数次，\(x_i = 1\)，否则 \(x_i = -1\)。
炒个例子，\(a = \{1, 1, 2, 2, 3, 3\}, x = \{1, -1, 1, -1, 1, -1\}\)
然后做三个前缀和，第一个前缀和是 \(qz1_i =\sum\limits_{i = 1}^n a_ix_i, qz2_i = \sum\limits_{i = 1}^n a_i^2x_i, qz3_i = \sum\limits_{i = 1}^n \sqrt{a_i}x_i\)
这个时候显而易见，对于区间 \([l, r]\)，那么如果 \(qz1_r - qz1_{l - 1} = 0,qz2_r - qz2_{l - 1} = 0, qz3_r - qz3_{l - 1} = 0\)，那么这个就很有可能每个元素出现了偶数次。
不过这有一个很大的问题，就是 \(qz2\) 很容易溢出，反正它只要 \(a = {1, 2, 3, \dots, 10^6}\) 那么 \(qz2\) 直接原地爆炸，由于我暂时联系不到 zty，所以我没办法去问一下他这个细节是怎么处理的。抛却这个细节不谈，那么是否会有一个解，能 hack 这个算法呢？
很显然，我们肯定能找到。这就像双模 hash 一样，它很难用数学方法推导出一个 hack 数据，它也是有概率出错的，但是它出错概率很小。不过 zty 始终强调他这个应该是对的还让我不要找了让我很不爽（不是（划掉（zty 巨佬别打我
后来我发现它溢出了，完结（
一种正常的做法
随机映射一下，然后我们就可以跑了，出错概率很小，可以随机搞 10 遍差不多。
标签：某道,le,limits,10,玄学,qz2,zty,sum From： https://www.cnblogs.com/thirty-two/p/17255315.html