#53350: 可以用prefix
Tino961009
(能AC，就別管怎麼AC)
學校
:
國立臺中第二高級中學
編號 : 288138
來源 : [111.82.100.143]
最後登入時間 ：
2025-10-11 12:15:02
用 t_q 表示 'Q' 的總和
q[i] 表示到目前為止有幾個'Q'
遇到'A'則儲存座標
接下來只要處理 A 座標( 以下為 X ) 即可
ans += q[x-1] * ( t_q - q[x-1] )
//#include<bits/stdc++.h>
using namespace std;
int main(){
string line;
getline(cin, line);
int t_q=0, n=line.size();
vector<int> q(n+1);
queue<int> d;
long long ans=0;
for(int i=1; i<=n; i++){
if(line[i-1]=='Q'){
t_q++;
}
else if(line[i-1]=='A') d.push(i);
q[i]=t_q;
}
while(d.size()){
int x=d.front();
d.pop();
ans+=q[x-1]*(t_q-q[x-1]);
}
cout<<ans<<endl;
return 0;
}