有个显然的小 trick：如果两个数相乘为平方数，那么消去平方因子后这两个数相等。
于是我们可以暴力枚举，每出现一个新数就加一，用 unordered_map 维护，然后就 T 了。
考虑优化。我们对于每个数预处理出上一个与它相等的数的位置。这样每次枚举的时候只需要看 \(pre_i\) 是否小于左边界即可。
注意特判一下 \(0\)。
复杂度 \(O(n^2)\)。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5000+5;
int n,a[N],ans[N],pre[N];
int fen(int x){
int flag=(x>=0?1:-1);
x=abs(x);
for(ll i=2;i*i<=x;++i){
ll t=i*i;
while(x%t==0)x/=t;
}
return x*flag;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
a[i]=fen(a[i]);
for(int j=i-1;j>=1;--j){
if(a[i]==a[j]){
pre[i]=j;
break;
}
}
}
for(int i=1;i<=n;++i){
bool flag=0;
int cnt=0;
for(int j=i;j<=n;++j){
if(a[j]==0)flag=1;
if(pre[j]<i)++cnt;
if(flag)++ans[max(cnt-1,1)];
else ++ans[cnt];
}
}
for(int i=1;i<=n;++i)cout<<ans[i]<<" ";
cout<<endl;
return 0;
}