题解：AT_abc441_e [ABC441E] A ＞ B substring

考虑定一求一，枚举左端点。

我们发现一个区间[ 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_r>S_{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。

#include<cstdio>#include<string>#include<iostream>#include<set>usingnamespacestd;intamb[500005],xval[500005];intxvv[1000010];intqsum(intx){x=500005-x;intsum=0;do{sum+=xvv[x];}while(x-=x&-x);returnsum;}voidqadd(intx,inty){x=500005-x;do{xvv[x]+=y;}while((x+=x&-x)<=1000005);}intmain(){intn;scanf("%d",&n);string str;cin>>str;intcc=0;set<int>st;for(inti=0;i<n;i++){xval[i]=(str[i]=='A'?1:(str[i]=='B'?-1:0));if(i==0)amb[i]=xval[i];elseamb[i]=amb[i-1]+xval[i];}intygg=0;longlongsum=0;for(inti=n-1;i>=0;i--){if(str[i]=='A')ygg++;if(str[i]=='B')ygg--;qadd(xval[i]-ygg,1);sum+=qsum(-ygg+1);}printf("%lld\n",sum);return0;}

:::