记录编号	596211	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO24 Open Silver]The 'Winning' Gene	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	6.019 s
提交时间	2024-10-23 19:06:42	内存使用	29.05 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define MAXN 3010
#define debug cout<<"flyfree\n";
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll n,cf[MAXN][MAXN],ans[MAXN][MAXN],cnt[MAXN];
ull p[MAXN],h[MAXN],f1[MAXN],f2[MAXN];
char c[MAXN];
ull get(ll l,ll r){
	return h[r]-h[l-1]*p[r-l+1];
}
ll lmp(ll l1,ll r1,ll l2,ll r2){
	ll l=1,r=r1-l1+1;
	while(l<r){
		ll mid=(l+r+1)/2;
//		cout<<l<<" "<<mid<<" "<<r<<endl;
		if(get(l1,l1+mid-1)==get(l2,l2+mid-1))l=mid;
		else r=mid-1;
	}
	if(l==1)return c[l1]==c[l2];
	else return l;
}
ll cmp(ll l1,ll r1,ll l2,ll r2){
	ll loc=lmp(l1,r1,l2,r2);
//	cout<<loc<<endl; 
	if(loc==r1-l1+1)return 1;
	else{
		if(c[l1+loc]==c[l2+loc])return 1;
		else if(c[l1+loc]<c[l2+loc])return 2;
		else return 0;
	}
}
void ycl(){
	p[0]=1;
	for(int i=1;i<=n;i++)p[i]=p[i-1]*131;
	for(int i=1;i<=n;i++)h[i]=h[i-1]*131+c[i];
}
void clear(){
	for(int i=1;i<=n;i++){
		f1[i]=0,f2[i]=n+1;
	}
}
int main(){
	freopen("winninggene.in","r",stdin);
	freopen("winninggene.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)cin>>c[i];
	ycl();
	for(int len=1;len<=n;len++){
		stack <ll> st;
		clear();
		for(int j=1;j+len-1<=n;j++){
			while(!st.empty()){
				if(cmp(j,j+len-1,st.top(),st.top()+len-1)==2)st.pop();
				else break;
			}
			if(!st.empty())f1[j]=st.top();
			st.push(j);
		}
		while(!st.empty())st.pop();
//		debug
		for(int j=n-len+1;j;j--){
//			debug
			while(!st.empty()){
//				debug;
//				cout<<st.top()<<" "<<cmp(j,j+len-1,st.top(),st.top()+len-1)<<endl;
				if(cmp(j,j+len-1,st.top(),st.top()+len-1))st.pop();
				else break;
			}
			if(!st.empty())f2[j]=st.top()+len-1;
			st.push(j);
		}
		for(int j=1;j+len-1<=n;j++){
//			cout<<j<<" "<<j+len-1<<" "<<f1[j]<<" "<<f2[j]<<endl;
//			cout<<len<<" "<<f2[j]-f1[j]-1<<endl;
			ans[len][len]++;
			ans[len][f2[j]-f1[j]]--;
		}
//		debug
	}
	for(int len=1;len<=n;len++){
		ll now=0;
		for(int j=len;j<=n;j++){
			now+=ans[len][j];
			cnt[now]++;
		}
	}
	for(int i=1;i<=n;i++)cout<<cnt[i]<<endl;
	return 0;
}