题解：P12024 [USACO25OPEN] It's Mooin' Time III B

· · 题解

思路

首先对于两个在区间 [l,r] 中的哞叫 (i,j,k_1),(i,j,k_2)，如果 k_1<k_2，那么显然后者更优。同理 (i_1,j,k),(i_2,j,k) 中如果 i_1<i_2，那么前者更优。因此对于每次询问我们枚举小写字母 c，只需要考虑 k\in[l,r] 且 s_k=c 的最大 k 和满足 i\in[l,r] 且 s_i\ne c 的最小 i 即可。可以二分求出。那么此时我们选取的 j 需要满足 j\in(i,k) 且 s_j=c，可以发现 j 越接近 \frac{i+k}{2}，哞叫 s_is_js_k 的值 (k-j)(j-i) 越大。因此可以二分求出 j。最后总复杂度 O(Q\log N)。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define DEBUG
#define FASTER_IO
int n,q;
int s[100005];
int mp[100005],mnp[26];
vector<int> pos[26];
int getnearest(const vector<int> &vec,int l,int r,int p) // get the nearest number of vec to p in [l,r]
{
    if(l>r)
        return -1;
    auto le=lower_bound(vec.begin(),vec.end(),l),ri=upper_bound(vec.begin(),vec.end(),r);
    if(ri<=le)
        return -1;
    else
    {
        if(p<*le)
            return *le;
        if(p>*(ri-1))
            return *(ri-1);
        auto rr=lower_bound(le,ri,p),ll=upper_bound(le,ri,p)-1;
        int lek=*ll,ril=*rr;
        if(p-lek<ril-p)
            return lek;
        else
            return ril;
    }
}
int getmax(const vector<int> &vec,int l,int r)
{
    return getnearest(vec,l,r,r+1);
}
int getmin(const vector<int> &vec,int l,int r)
{
    return getnearest(vec,l,r,l-1);
}
signed main()
{
    #ifdef FASTER_IO
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    #define endl "\n"
    #endif
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        char c;
        cin>>c;
        s[i]=c-'a';
        pos[s[i]].push_back(i);
    }
    for(int i=0;i<26;i++)
        mnp[i]=n+1;
    for(int i=n;i>=1;i--)
    {
        mp[i]=n+1;
        for(int j=0;j<26;j++)
            if(j!=s[i])
                mp[i]=min(mp[i],mnp[j]);
        mnp[s[i]]=i;
    }
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        long long ans=-1;
        for(int i=0;i<26;i++)
        {
            int mx=getmax(pos[i],l,r);
            if(mx==-1)
                continue;
            int p3=mx,p1=(s[l]==i?mp[l]:l);
            int p2=getnearest(pos[i],l,r,(p1+p3)/2);
            int p22=getnearest(pos[i],l,r,(p1+p3+1)/2);
            #ifdef DEBUG
            cout<<"p2="<<p2<<",p22="<<p22<<endl;
            #endif
            if(abs(p22-(p1+p3)/2.0)<abs(p2-(p1+p3)/2.0))
                p2=p22;
            if(p1<p2&&p2<p3)
            {
                #ifdef DEBUG
                cout<<"choose"<<p1<<","<<p2<<","<<p3<<endl;
                #endif
                ans=max(ans,1ll*(p3-p2)*(p2-p1));
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
/*
12 1
abcabbacabac
1 12
*/