题解

本题使用前缀和 + 枚举求解字符串匹配计数问题。

算法思路：

1. 问题分析：

   • 字符串只包含 J、O、I 三种字符
   • 需要统计满足条件的三元组 $(i, j, k)$：$i < j < k$，且 $str[i] = \text{J}$，$str[j] = \text{O}$，$str[k] = \text{I}$
   • 目标是最大化某种特定的计数方式

2. 前缀和预处理：

   • sj[i]：前 $i$ 个字符中 J 的数量（前缀和）
   • si[i]：从位置 $i$ 到末尾的 I 的数量（后缀和）
   • sjo[i]：对于每个 O，统计其左边的 J 的数量累加和
   • soi[i]：对于每个 O，统计其右边的 I 的数量累加和

3. 答案计算：

   • 基础答案：对于每个 I，累加其左边所有 O 对应的 J 数量之和
     • $ans = \sum_{str[i] = \text{I}} sjo[i]$
   • 最大化贡献：枚举每个位置 $i$，计算 $sj[i] \times si[i]$（左边 J 数量 × 右边 I 数量）
     • 这表示以位置 $i$ 为中心的最大贡献
   • 同时考虑 $sjo[n]$ 和 $soi[1]$ 作为候选答案

4. 输出结果：

   • 答案为基础答案加上最大贡献：$ans + \max(Max)$

时间复杂度：$O(n)$，只需要一次遍历和前缀和计算。

本题的关键在于理解如何通过前缀和快速统计满足条件的三元组数量。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define bll __int128
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define sec second
#define vii vector<int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pii pair<int,int>
#define pil pair<int,ll>
#define re register
#define puu pair<ull,ull>
#define clr clear
#define vpi vector<pii>
#define qii queue<int>
using namespace std;
namespace io{
	const int __SIZE=(1<<22)+1;
	char ibuf[__SIZE],*iS,*iT,obuf[__SIZE],*oS=obuf,*oT=oS+__SIZE-1,__c,qu[55];int __f,qr,_eof;
#define Gc()(iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,__SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
	inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
	inline void gc(char&x){x=Gc();}
	inline void pc(char x){*oS++=x;if(oS==oT)flush();}
	inline void pstr(const char*s){int __len=strlen(s);for(__f=0;__f<__len;++__f)pc(s[__f]);}
	inline void gstr(char*s){for(__c=Gc();__c<32||__c>126||__c==' ';)__c=Gc();
		for(;__c>31&&__c<127&&__c!=' ';++s,__c=Gc())*s=__c;*s=0;}
	template<class I>inline bool read(I&x){_eof=0;
		for(__f=1,__c=Gc();(__c<'0'||__c>'9')&&!_eof;__c=Gc()){if(__c=='-')__f=-1;_eof|=__c==EOF;}
		for(x=0;__c<='9'&&__c>='0'&&!_eof;__c=Gc())x=x*10+(__c&15),_eof|=__c==EOF;x*=__f;return!_eof;}
	template<class I>inline void write(I x){if(!x)pc('0');if(x<0)pc('-'),x=-x;
		while(x)qu[++qr]=x%10+'0',x/=10;while(qr)pc(qu[qr--]);}
	struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}using io::pc;using io::gc;using io::pstr;using io::gstr;using io::read;using io::write;
const int N=1e5+5;
int sj[N],si[N],sjo[N],soi[N];
string str;
int n;
int main()
{
	cin>>n>>str,str=' '+str;
	for(int i=1;i<=n;i++)
	{
		if(str[i]=='J')sj[i]++;
		else if(str[i]=='I')si[i]++;
	}
	for(int i=1;i<=n;i++)sj[i]+=sj[i-1];
	for(int i=n;i>=1;i--)si[i]+=si[i+1];
	for(int i=1;i<=n;i++)if(str[i]=='O')sjo[i]=sj[i],soi[i]=si[i];
	for(int i=1;i<=n;i++)sjo[i]+=sjo[i-1];
	for(int i=n;i>=1;i--)soi[i]+=soi[i+1];
	ll ans=0,Max=max(sjo[n],soi[1]);
	for(int i=1;i<=n;i++)if(str[i]=='I')ans+=sjo[i];
	for(int i=1;i<=n;i++)Max=max(Max,1ll*sj[i]*si[i]);
	printf("%lld",ans+Max);
}