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

· · 题解

思路

先预处理一个字符集 c，c_{i,j} 表示字符 i 的第 j 次出现实在字符串 s 的第几位。

对于每次询问，

  1. 枚举三元组中第一个字符 i（不是下标，是字符！），接着在 c_i 中查找 \ge l 的第一个下标 p1。
  2. 枚举最后一个字符 k（注意不能与 i 相等），接着在 c_k 中查找 \le r 的最后一个下标 p3。
  3. 在 c_k 中查找最接近 \lfloor \frac{i+k}{2} \rfloor 的下标 p2。
  4. 更新答案（实际上写代码时会找在左边和右边最接近 \lfloor \frac{i+k}{2} \rfloor 的最大值来更新答案）。
  5. 输出答案 （废话）。
  6. 十年 OI 一场空，不开 long long 见祖宗。

代码

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

vector<int> c[50];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,q,l,r;
    string s;
    cin>>n>>q>>s;
    for(int i = 0; i < n; i++){
        c[s[i]-'a'].push_back(i);
    }
    int i,j,k;
    long long ans;
    while(q--){
        cin>>l>>r;
        l--;r--;
        ans = -1;
        for(int c1 = 0; c1 < 26; c1++){
            i = lower_bound(c[c1].begin(),c[c1].end(),l)-c[c1].begin();
            if(i>=c[c1].size() || i>=r-1){
                continue;
            }
            for(int c3 = 0; c3 < 26; c3++){
                if(c3==c1 || c[c3].size()<2){
                    continue;
                }
                k = upper_bound(c[c3].begin(),c[c3].end(),r)-c[c3].begin()-1;
                if(k<=0 || c[c3][k-1]<=c[c1][i]){
                    continue;
                }
                j = upper_bound(c[c3].begin(),c[c3].end(),(c[c3][k]+c[c1][i])/2)-c[c3].begin();
                if(j < k){
                    ans = max(ans,(c[c3][k]-c[c3][j])*1LL*(c[c3][j]-c[c1][i]));
                }
                j--;
                if(j>=0 && c[c1][i]<c[c3][j]){
                    ans = max(ans,(c[c3][k]-c[c3][j])*1LL*(c[c3][j]-c[c1][i]));
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}