记录编号	600968	评测结果	AAAAAAAAAAAAAAA
题目名称	4040.[USACO24 Open Silver]The 'Winning' Gene	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	20.155 s
提交时间	2025-05-22 15:17:45	内存使用	4.46 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3010;

int ans[N],l[N],r[N],a[N];
int n;
string s;

signed main(){
	freopen("winninggene.in","r",stdin);
	freopen("winninggene.out","w",stdout); 
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	cin>>s;
	for(int L=1;L<=n;L++){
		for(int i=0;i<=n;i++)a[i]=0,l[i]=-1,r[i]=n-L+1;
		stack<pair<int,string>>st;
		string nw=s.substr(0,L);
		st.push({0,nw});
		for(int i=1;i<=n-L;i++){
			nw.erase(nw.begin());nw+=s[i+L-1];
			while(!st.empty()&&st.top().second>nw)st.pop();
			if(!st.empty())l[i]=st.top().first;
			st.push({i,nw});
		}
		while(!st.empty())st.pop();
		nw=s.substr(n-L,L);
		st.push({n-L,nw});
		for(int i=n-L-1;i>=0;i--){
			nw.erase(nw.end()-1);nw=s[i]+nw;
			while(!st.empty()&&st.top().second>=nw)st.pop();
			if(!st.empty())r[i]=st.top().first;
			st.push({i,nw});
		}
		for(int i=0;i<=n-L;i++){
			a[L]++;
			a[L+r[i]-l[i]-1]--;//(L+r[i]-l[i]-2)+1
		}
		for(int k=L;k<=n;k++){
			a[k]+=a[k-1];
			ans[a[k]]++;
		}
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
	return 0;
}