Codeforces 137 E. Last Chance

問題

文字列が与えられる。
この文字列の連続する部分文字列で、母音の数が子音の数の2倍以下であるようなものを、goodなsubstringという。
goodなsubstringで、長さ最長のものの長さおよび、その長さのgoodなsubstringが現れる回数を求めよ。

制約条件

文字列の長さ≦2*10^5

方針

尺取法。
a[i]をi文字目が母音のとき-1,子音のとき+2とする。
s[i]をa[i]の累積和とする。


すると、s[i]-s[j]≧0となることが、文字列のj文字目からi文字目がgoodなsubstringになることに対応する。
各jに対してs[i]-s[j]≧0になるような最も大きいiを求められればよい。


これは、(s[i],i),(-s[j],j)をあらかじめソートしておくことによりできる。
-s[j]は小さい順に、s[i]は大きい順に見て、
-s[j]+s[i]≧0の間iを小さくしつづけて、その中でのiのインデックスの最大値を取る。


これを繰り返して、goodなsubstringの長さの最大値およびその個数を求めればよい。

ソースコード

int n,a[200001],s[200001];
string in;

void run()
{
	cin>>in;
	n=in.size();
	rep(i,n){
		char c=tolower(in[i]);
		if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')a[i]=-1;
		else a[i]=2;
	}
	s[0]=0;
	rep(i,n)s[i+1]=s[i]+a[i];
	vector<pi> M,P;
	rep(i,n+1){
		M.pb(mp(-s[i],i));
		P.pb(mp(s[i],i));
	}
	sort(all(M)); sort(all(P));
	int i=0,j=n,len=0,ans=0;
	set<int> s;
	for(;i<=n;i++){
		while(j>=0&&P[j].first+M[i].first>=0)s.insert(-P[j--].second);
		if(-*s.begin()-M[i].second>len)len=-*s.begin()-M[i].second,ans=0;
		if(-*s.begin()-M[i].second==len)ans++;
	}
	if(len==0)cout<<"No solution"<<endl;
	else cout<<len<<" "<<ans<<endl;
}