题解：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)

。

代码

CPP

#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
*/

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

文章操作

思路

代码

相关推荐

评论

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