自动搬运

查看原文

来自洛谷，原作者为

	IcyDragon 求关！！！ || 看主页：/paste/ms73vnw8

搬运于2025-08-24 23:12:13，当前版本为作者最后更新于2025-04-07 22:17:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

先预处理一个字符集 $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;
}