记录编号	600046	评测结果	AAAAAAAAAAA
题目名称	[USACO25 Open Bronze]It s Mooin Time III	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	1.064 s
提交时间	2025-04-12 15:18:02	内存使用	4.13 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define maxn 200005

int n, q, num[26][maxn], cnt[26];
string s;

signed main() {
		freopen("Time.in","r",stdin);
				freopen("Time.out","w",stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q >> s; s = ' ' + s;
    for(int i = 1; i <= n; ++i) {
        int c = s[i] - 'a';
        num[c][++cnt[c]] = i;
    }
    while(q--) {
        int l, r, ans = 0; cin >> l >> r;
        for(int c = 0; c < 26; ++c) {
            if(cnt[c] < 2) continue;
            int R = upper_bound(num[c]+1, num[c]+cnt[c]+1, r) - num[c] - 1;
            if(R < 2) continue;
            int L = lower_bound(num[c]+1, num[c]+R+1, l) - num[c];
            if(L >= R) continue;
            
            int d = l;
            while(d <= r && s[d]-'a' == c) ++d; 
            if(d > r) continue; 
            
            int k = upper_bound(num[c]+L, num[c]+R+1, d) - num[c];
            if(k > R) continue;
            
            int mid = (d + num[c][R]) / 2;
            int h = upper_bound(num[c]+k, num[c]+R+1, mid) - num[c];
            int t1 = h <= R ? (num[c][R] - num[c][h]) * (num[c][h] - d) : 0;
            int t2 = h > k ? (num[c][R] - num[c][h-1]) * (num[c][h-1] - d) : 0;
            ans = max({ans, t1, t2});
        }
        cout << (ans ? ans : -1) << endl;
    }
    return 0;
}