[Algo Beat Contest 002 C] Counting Square Numbers

joe_zxq · 2025-03-02 17:32:34 · 题解

首先考虑预处理出一个前缀和，枚举所有 n^2 个区间计算区间和并判断是否为完全平方数。假设当前区间为 [L,R]，则需要对于区间内的每一位，其对应的答案都会增加 1。于是考虑维护差分数组，最终前缀和一下就是答案啦。

当然，也可以无脑地用树状数组或线段树来实现区间加，但是这是 C 题。

时间复杂度：差分做法为 O(n^2)，数据结构做法为 (n^2 \log n)。

下面展示的是差分做法。

#include<bits/stdc++.h>
using namespace std;
long long a[100005],b[100005];
bool chk(long long x){
    long long y=sqrt(x);
    return y*y==x;
}
int main(){
    long long n;
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[i]=a[i-1]+a[i];
    }
    for(long long i=1;i<=n;i++){
        for(long long j=i;j<=n;j++){
            long long sum=a[j]-a[i-1];
            if(chk(sum)){
                b[i]++;
                b[j+1]--;
            }
        }
    }
    for(long long i=1;i<=n;i++)
        b[i]+=b[i-1];
    for(long long i=1;i<=n;i++){
        printf("%lld\n", b[i]);
    }
    return 0;
}