考虑定一求一枚举左端点。我们发现一个区间[ l , r ] [l,r][l,r]满足条件等价于c n t A r − c n t A l − 1 c n t B r − c n t B l − 1 \mathrm{cntA}_r - \mathrm{cntA}_{l-1} \mathrm{cntB}_r - \mathrm{cntB}_{l-1}cntAr​−cntAl−1​cntBr​−cntBl−1​其中c n t A \mathrm{cntA}cntA和c n t B \mathrm{cntB}cntB分别表示前缀A \texttt AA和B \texttt BB的数量也就是c n t A r − c n t B r c n t A l − 1 − c n t B l − 1 \mathrm{cntA}_r - \mathrm{cntB}_r\mathrm{cntA}_{l-1}-\mathrm{cntB}_{l-1}cntAr​−cntBr​cntAl−1​−cntBl−1​。那我们就用S i S_iSi​来表示c n t A i − c n t B i \mathrm{cntA}_i - \mathrm{cntB}_icntAi​−cntBi​。注意到S r − S l − 1 0 S_r-S_{l-1}0Sr​−Sl−1​0等价于S r S l − 1 S_rS_{l-1}Sr​Sl−1​也就是 $S_r\ge S_{l-1}1$然而需要满足r ≥ l r\ge lr≥l。那么在l ll右移一位的时候删除掉原来的l ll的S SS值然后累加答案即可。使用树状数组即可树状数组处理后缀信息和前缀一样是 trivial 的。我的代码里用的是反过来处理的方式即左端点从右往左动。也是类似的。:::info[代码提交记录]submission。#includecstdio#includestring#includeiostream#includesetusingnamespacestd;intamb[500005],xval[500005];intxvv[1000010];intqsum(intx){x500005-x;intsum0;do{sumxvv[x];}while(x-x-x);returnsum;}voidqadd(intx,inty){x500005-x;do{xvv[x]y;}while((xx-x)1000005);}intmain(){intn;scanf(%d,n);string str;cinstr;intcc0;setintst;for(inti0;in;i){xval[i](str[i]A?1:(str[i]B?-1:0));if(i0)amb[i]xval[i];elseamb[i]amb[i-1]xval[i];}intygg0;longlongsum0;for(intin-1;i0;i--){if(str[i]A)ygg;if(str[i]B)ygg--;qadd(xval[i]-ygg,1);sumqsum(-ygg1);}printf(%lld\n,sum);return0;}:::