思路:
虽说可以用莫队解决, 但是这个数据范围意味着需要一点高深的卡常技巧.
有一个十分神奇的线段树解法:
使用线段树维护最大值, 最小值, 以及平方和.
对于每个询问, 首先判断最大值与最小值之差是否为区间长度-1, 然后比对最小值到最大值的连续平方和与求得的区间平方和即可. 连续平方和可以用公式求解.
“平方和”相当于给区间做了一个哈希, 所以不需要精确的平方和值, 取模即可.
代码:
1 |
|
虽说可以用莫队解决, 但是这个数据范围意味着需要一点高深的卡常技巧.
有一个十分神奇的线段树解法:
使用线段树维护最大值, 最小值, 以及平方和.
对于每个询问, 首先判断最大值与最小值之差是否为区间长度-1, 然后比对最小值到最大值的连续平方和与求得的区间平方和即可. 连续平方和可以用公式求解.
“平方和”相当于给区间做了一个哈希, 所以不需要精确的平方和值, 取模即可.
1 | #include <cstdio> |