題目描述：
Elsie 正在試圖向 Bessie 描述她最喜歡的 USACO 競賽，但 Bessie 很難理解為什麼 Elsie 這麼喜歡它。Elsie 説「現在是哞哞時間！誰想哞哞？請，我只想參加 USACO」。
Bessie 仍然不理解，於是她將 Elsie 的描述轉文字得到了一個長為 （）的字符串，包含小寫字母字符 。Elsie 認為一個包含三個字符的字符串 是一個哞叫，如果 且 。
一個三元組 是合法的，如果 且字符串

• FJ 將字符串 在索引
• 該三元組的值是

換句話説，該三元組的值等於 。
Bessie 向你進行 （）個查詢。在每個查詢中，她給你兩個整數 和 （，），並詢問滿足 和 的所有合法三元組 的最大值。如果不存在合法的三元組，輸出 。
注意這個問題涉及到的整數可能需要使用 64 位整數類型（例如，C/C++ 中的 long long）。

輸入格式：
輸入的第一行包含兩個整數 和 。
以下一行包含 。
以下 行每行包含兩個整數 和 ，表示每個查詢。
輸出格式：
對於每一個查詢輸出一行，包含對於該查詢的答案。

奶牛時間（三） It’s Mooin’ Time III B

題目大意

一個包含三個字符的字符串 ，如果 且 ，則字符串

一個三元組 ，如果 且字符串 組成一個哞叫，則這個三元組是合法的，該三元組的值等於 。

輸入一個長為 （）的字符串，包含小寫字母字符 。

接下來會有 （）個查詢。在每個查詢中，給出兩個整數 和 （，），並詢問滿足 和 的所有合法三元組 的最大值。如果不存在合法的三元組，輸出 。

題目分析

這道題我們採用貪心策略和二分優化，在區間 中，我們枚舉這個區間中所出現過的字符 ，找兩個位置 ，使 ，則 就充當 ，對於 ，我們可以確定 應為區間 中最後一個字符 ，而 應從區間 第一個字符 枚舉到最後一個字符 之前，在此過程中， 一直不變，即為區間 中第一個不為

解法步驟

1. 將給出的字符串中出現的字符分類，統計每種字符出現的位置，在每次詢問中，執行以下操作：
2. 給出區間 ，遍歷字符串中出現的每種字符 （即使在區間
3. 找到區間 中第一個與 不相同的字符的位置，記錄為 （枚舉即可）；
4. 找到區間 中最後一個 字符，記錄其位置為 ，找到區間 中第一個 字符，記錄其指針為 ，指針 向後枚舉（字符
5. 所指的位置即為 ，本次得到的三元組的值為 ，更新結果 。

代碼指導

1. 可以使用 vector 容器儲存每種字符
2. 可以使用語句 auto it=upper_bound(G[id].begin(),G[id].end(),l); 來找到區間中字符
3. 可以使用語句 auto itt=upper_bound(G[id].begin(),G[id].end(),r);itt--; 來找到區間中字符
4. 在 位置枚舉過程中，可以添加語句 if ((long long)d*_d<=num) break;，表示如果當前的 小於或等於已有的 就可以不再繼續枚舉，因為

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
char s[N];
vector<int>G[N],K;
map<char,int>mp;
int main()
{
	int n,q,id=0;
	scanf("%d%d",&n,&q);
	scanf("%s",s+1);
	for (int i=1; i<=n; i++)
	{
		if (!mp[s[i]]) mp[s[i]]=++id;
		G[mp[s[i]]].push_back(i);
	}
	for (int i=1; i<=n; i++) K.push_back(mp[s[i]]);
	sort(K.begin(),K.end());
	K.erase(unique(K.begin(),K.end()),K.end());
	while (q--)
	{
		int l,r;
		long long ans=-1;
		scanf("%d%d",&l,&r);
		for (int id : K)
		{
			long long num=-1;
			auto it=upper_bound(G[id].begin(),G[id].end(),l);
			auto itt=upper_bound(G[id].begin(),G[id].end(),r);
			itt--;
			int e=l;
			while (mp[s[e]]==id) e++;
			while (it!=itt&&it!=G[id].end()&&*it<=e) it++;
			while (it!=itt&&it!=G[id].end())
			{
				int d=*it-e;
				int _d=*itt-*it;
				if ((long long)d*_d<=num) break;
				num=max(num,(long long)d*_d);
				it++;
			}
			ans=max(ans,num);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

時間複雜度

有 次詢問，枚舉字符 有 種， 枚舉的次數為 ，時間複雜度為 。

作者：ZZA000HAH