记录编号	600044	评测结果	AAAAAAAAATT
题目名称	[USACO25 Open Bronze]It s Mooin Time III	最终得分	82
用户昵称	wdsjl	是否通过	未通过
代码语言	C++	运行时间	5.650 s
提交时间	2025-04-12 15:06:42	内存使用	3.99 MiB

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
#define int long long

vector <int> s[50];

int n,q,l,r,res;
int ii,jj,kk;
string c;

signed main(){
	freopen("Time.in","r",stdin);
	freopen("Time.out","w",stdout);
//	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	scanf("%lld%lld",&n,&q);
	cin>>c;
//	scanf("%s",&c);
	for(int i=0;i<n;i++){
		s[c[i]-'a'].push_back(i);
	} 
	while(q--){
		scanf("%lld%lld",&l,&r);
		l--;
		r--;
		res=-1;
		for(int c1 = 0; c1 < 26; c1++){
			ii = lower_bound(s[c1].begin(),s[c1].end(),l)-s[c1].begin();
			if(ii>=s[c1].size() || ii>=r-1){
				continue;
			}
			for(int c3 = 0; c3 < 26; c3++){
				if(c3==c1 || s[c3].size()<2){
					continue;
				}
				kk = upper_bound(s[c3].begin(),s[c3].end(),r)-s[c3].begin()-1;
				if(kk<=0 || s[c3][kk-1]<=s[c1][ii]){
					continue;
				}
				jj = upper_bound(s[c3].begin(),s[c3].end(),(s[c3][kk]+s[c1][ii])/2)-s[c3].begin();
				if(jj < kk){
					res = max(res,(s[c3][kk]-s[c3][jj])*1LL*(s[c3][jj]-s[c1][ii]));
				}
				jj--;
				if(jj>=0 && s[c1][ii]<s[c3][jj]){
					res = max(res,(s[c3][kk]-s[c3][jj])*1LL*(s[c3][jj]-s[c1][ii]));
				}
			}
		}
		printf("%lld\n",res); 
	}
	return 0;
}