P12024 [USACO25OPEN] It’s Mooin’ Time III B

题目描述

Elsie 正在试图向 Bessie 描述她最喜欢的 USACO 竞赛，但 Bessie 很难理解为什么 Elsie 这么喜欢它。Elsie 说「现在是哞哞时间！谁想哞哞？拜托，我只想参加 USACO」。

Bessie 仍然不理解，于是她将 Elsie 的描述转文字得到了一个长为NNN（3≤N≤1053 \leq N \leq 10^53≤N≤105）的字符串，包含小写字母字符s1s2…sNs_1s_2 \ldots s_Ns1​s2​…sN​。Elsie 认为一个包含三个字符的字符串ttt是一个哞叫，如果t2=t3t_2 = t_3t2​=t3​且t2≠t1t_2 \neq t_1t2​=t1​。

一个三元组(i,j,k)(i, j, k)(i,j,k)是合法的，如果i<j<ki < j < ki<j<k且字符串sisjsks_i s_j s_ksi​sj​sk​组成一个哞叫。对于该三元组，FJ 执行以下操作计算其值：

• FJ 将字符串sss在索引jjj处弯曲 90 度
• 该三元组的值是Δijk\Delta ijkΔijk的面积的两倍。

换句话说，该三元组的值等于(j−i)(k−j)(j-i)(k-j)(j−i)(k−j)。

Bessie 向你进行QQQ（1≤Q≤3⋅1041 \leq Q \leq 3 \cdot 10^41≤Q≤3⋅104）个查询。在每个查询中，她给你两个整数lll和rrr（1≤l≤r≤N1 \leq l \leq r \leq N1≤l≤r≤N，r−l+1≥3r-l+1 \ge 3r−l+1≥3），并询问满足l≤il \leq il≤i和k≤rk \leq rk≤r的所有合法三元组(i,j,k)(i, j, k)(i,j,k)的最大值。如果不存在合法的三元组，输出−1-1−1。

注意这个问题涉及到的整数可能需要使用 64 位整数类型（例如，C/C++ 中的long long）。

输入格式

输入的第一行包含两个整数NNN和QQQ。
以下一行包含s1s2,…sNs_1 s_2, \ldots s_Ns1​s2​,…sN​。

以下QQQ行每行包含两个整数lll和rrr，表示每个查询。

输出格式

对于每一个查询输出一行，包含对于该查询的答案。

输入输出样例 #1

输入 #1

12 5 abcabbacabac 1 12 2 7 4 8 2 5 3 10

输出 #1

28 6 1 -1 12

说明/提示

样例解释

对于第一个查询，(i,j,k)(i,j,k)(i,j,k)必须满足1≤i<j<k≤121 \le i < j < k \le 121≤i<j<k≤12。可以证明，对于某个合法的(i,j,k)(i,j,k)(i,j,k)，Δijk\Delta ijkΔijk的最大面积在i=1i=1i=1，j=8j=8j=8以及k=12k=12k=12时取到。注意s1s8s12s_1 s_8 s_{12}s1​s8​s12​是字符串 “acc”，根据前述定义是一个哞叫。Δijk\Delta ijkΔijk的直角边长为777和444，从而它的面积的两倍将等于282828。

对于第三个查询，(i,j,k)(i,j,k)(i,j,k)必须满足4≤i<j<k≤84 \le i < j < k \le 84≤i<j<k≤8。可以证明，对于某个合法的(i,j,k)(i,j,k)(i,j,k)，Δijk\Delta ijkΔijk的最大面积在i=4i=4i=4，j=5j=5j=5以及k=6k=6k=6时取到。

对于第四个查询，不存在满足2≤i<j<k≤52 \le i < j < k \le 52≤i<j<k≤5的(i,j,k)(i,j,k)(i,j,k)使得sisjsks_i s_j s_ksi​sj​sk​是一个哞叫，所以该查询的输出为−1-1−1。

测试点性质

• 测试点2∼32\sim32∼3：N,Q≤50N,Q\le 50N,Q≤50。
• 测试点4∼64\sim64∼6：Q=1Q=1Q=1，唯一的询问满足l=1l=1l=1且r=Nr=Nr=N。
• 测试点7∼117\sim 117∼11：没有额外限制。

C++实现

#include<iostream>#include<algorithm>#include<vector>#include<string>usingnamespacestd;vector<int>c[50];intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);intn,q,l,r;string s;cin>>n>>q>>s;for(inti=0;i<n;i++){c[s[i]-'a'].push_back(i);}inti,j,k;longlongans;while(q--){cin>>l>>r;l--;r--;ans=-1;for(intc1=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(intc3=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';}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容