关于维护平方和立方和

提供一组hack数据，目前所有基于维护平方和立方和的题解都挂了：

CPP

25 1
1 1 4 4 6 6 7 7 10 10 11 11 13 13 16 16 17 2 3 5 8 9 12 14 15
2 1 17

实际上即使维护4次方和5次方和之类的也都是没用的，因为有这样一个神奇的性质（可惜我并不会证明）：

对于任意正整数n，将0~2^n-1按照二进制1的个数的奇偶性分成2组，则对于任意i=0~n-1，这两组数的i次方和都相等。

然后在两个集合里添加相同的数，把一个集合补成连续段并使得两个集合的(max-min)相等，就构造出了一组反例。

为了过掉这种数据需要维护logn个次方和才行，这题n<=5e5，需要维护到20次方和才能过（不知道还有没有什么方法能把20次方也卡掉）。

除此之外我目前想到的最好的确定性做法是维护区间有多少个不同的数，但是支持单点修改的话貌似是要带修主席树2个log吧。

至于其他非确定性算法，比如区间维护x^ai再hash，随机映射再xor之类的，目前没想到hack方法。

讨论操作