记录编号	600038	评测结果	AAAAAATTTAA
题目名称	[USACO25 Open Bronze]It s Mooin Time III	最终得分	73
用户昵称	htl	是否通过	未通过
代码语言	C++	运行时间	6.639 s
提交时间	2025-04-12 13:57:34	内存使用	17.90 MiB

#include<bits/stdc++.h>
using namespace std;
char s[100010];
long long n,q,l,r,tl,tr,ti,tk,tj;
int v1[28][100010];
int v2[28][100010];
int main()
{
    freopen("Time.in","r",stdin);
    freopen("Time.out","w",stdout);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    for(int i=1;i<=26;i++)
    {
        int tmp=-1;
        for(int j=1;j<=n;j++)
        {
            if(s[j]==char(i-1+'a'))
            {
                tmp=j;
            }
            v1[i][j]=tmp;
        }
        tmp=-1;
        for(int j=n;j>=1;j--)
        {
            if(s[j]==char(i-1+'a'))
            {
                tmp=j;
            }
            v2[i][j]=tmp;
        }
    }
    while(q--)
    {
        cin>>l>>r;
        long long ans=-1;
        for(int i=1;i<=26;i++)
        {
            tk=v1[i][r];
            ti=100000000;
            for(int j=1;j<=26;j++)
            {
                if(i!=j)
                {
                    if(v2[j][l]!=-1)
                    ti=min(ti,(long long)v2[j][l]);
                }
            }
            if(ti==-1)
            {
                continue;
            }
            tr=v1[i][tk-1];
            tl=v2[i][ti];
            if(tr<1||tl<1)
            continue;
            tj=-1;
            long long m1=-10,m2=-10;
            while(tr-tl>2)
            {
                if(m1==v1[i][tl+(tr-tl)/3]&&m2==v2[i][tr-(tr-tl)/3])
                break;
                m1=v1[i][tl+(tr-tl)/3];
                m2=v2[i][tr-(tr-tl)/3];
                if((m1-ti)*(tk-m1)>(m2-ti)*(tk-m2))
                tr=m2;
                else
                tl=m1;
            } 
            for(int j=tl;j<=tr;j=v2[i][j+1])
            {
                tj=max((v1[i][j]-ti)*(tk-v1[i][j]),tj);
            }
            ans=max(ans,tj);
        }
        cout<<ans<<endl;
    }
    return 0;
}