珂朵莉与宇宙

题目描述

星神是来自宇宙的

所以珂朵莉也是吧

所以我就出了个题

给你一个长为n的序列a，有n*(n+1)/2个子区间，问这些子区间里面和为完全平方数的子区间个数

输入描述:

第一行一个数n
第二行n个数表示序列a

输出描述:

输出一个数表示答案

示例1

输入
6
0 1 0 9 1 0

输出
11

备注:

1 <= n <= 100000
0 <= ai <= 10

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld

问题分析:

求区间和自然想到用前缀和，但由于要统计满足条件的区间和个数，而n最大有图片说明 ，因此直接暴力必定TLE。分析条件，需要寻找的是区间和为完全平方数的区间，那就可以直接枚举完全平方数。
根据图片说明 ，可知图片说明 ，这样，我们可以通过更新满足条件的前缀和的个数，不断进行累加，即可得到答案。AC代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int MAX = 1e5 * 10 + 10;

int cnt[MAX], s[N];   // cnt[]存储满足条件的区间出现的次数，s[]为前缀和数组

int main()
{
    ll n, x, ans = 0;
    cin >> n;

    for(ll i = 1; i <= n; i ++){   // 初始化前缀和数组
        cin >> x;
        s[i] = s[i - 1] + x;
    }

    cnt[0] = 1;
    for(ll i = 1; i <= n; i ++){
        for(ll j = 0; j * j <= s[i]; j ++)   // 从0到当前前缀和枚举完全平方数
            ans += cnt[s[i] - j * j];   // 前缀和为s[i] - j * j的个数累加
        cnt[s[i]] ++;   // 更新当前前缀和出现的次数
    }
    cout << ans << endl;
    return 0;
}