题目描述
克里斯托瓦尔有一个包含 $N$ 个整数（可能为负）的数组。
其中的第 $i$ 个数为 $A_i$。
如果其中的一个连续非空子数组的元素和是完全平方数，那么我们称该子数组是完美的。
若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。
例如，前 5 个完全平方数是 0,1,4,9,16。
请问克里斯托瓦尔的数组中共有多少个完美子数组。
只要两个子数组的起始位置或结束位置不同，即使它们以相同的顺序包含相同的数，我们也认为两个子数组是不同的。
输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。
对于每组数据，第一行包含整数 $N$。
第二行包含 $N$ 个整数，其中第 $i$ 个是 $A_i$。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为 Case #x: y，其中 $x$ 为组别编号（从 1 开始），$y$ 为完美子数组的数量。
输入样例
3
3
2 2 6
5
30 30 9 1 30
4
4 0 0 16
输出样例
Case #1: 1
Case #2: 3
Case #3: 9
样例解释
在示例 $1$ 中，只有一个完美子数组 $[2 2]$，其元素和为 $22$。
在示例 $2$ 中，共有 $3$ 个完美子数组：
-
[9]，其元素和为 $3^2$。 -
[1]，其元素和为 $1^2$。 -
[30 30 9 1 30]，其元素和为 $10^2$。
在示例 $3$ 中，共有 $9$ 个完美子数组：
-
[4]，其元素和为 $2^2$。 -
[4 0]，其元素和为 $2^2$。 -
[4 0 0]，其元素和为 $2^2$。 -
[0]，其元素和为 $0^2$。 -
[0 0]，其元素和为 $0^2$。 -
[0 0 16]，其元素和为 $4^2$。 -
[0]，其元素和为 $0^2$。 -
[0 16]，其元素和为 $4^2$。 -
[16]，其元素和为 $4^2$。
算法1
(区间和 + 模拟位置) $O(n + sqrt(S))$
-
s数组用来枚举区间和
-
a数组模拟位置
-
首先将a[M] = 1 表示a[0] 位置有数
-
然后求根当前区间和sqrt(S[i]), 然后用j枚举0 ~ sqrt(S)
-
若a[M + S - j * j] 的位置值为1，则表示当前有一个满足完美子数组的区间，加上该位置重复次数
-
这里还有一个minv，s[i] - minv 表示当前当前段幂值最大的极限，
-
最后还要将a[M + S] + 1 表示该位置有数，若为2，则表示该位置重复了两次
-
最后还要将每个位置的数进行还原
时间复杂度
枚举每个元素和 当前区间和内求根的枚举
参考文献
C++ 代码
#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 1e7;
int T;
int n;
int s[N], a[M * 2 + 10];
LL ans;
int main()
{
cin >> T;
for(int i = 1; i <= T; i ++) {
cin >> n;
int minv = 0;
ans = 0;
a[M] = 1;
int *p = a + M;
for(int i = 1; i <= n; i ++) {
cin >> s[i];
p += s[i];
s[i] += s[i - 1];
//s[i] - minv 表示当前当前段幂值最大的极限
for(int j = sqrt(s[i] - minv); j >= 0; j --) {
ans += *(p - j * j);
}
(*p) ++;
minv = min(minv, s[i]);
}
//恢复
for(int i = 0; i <= n; i ++) {
a[s[i] + M] --;
}
cout << "Case #" << i << ": " << ans << endl;
}
return 0;
}
