Submission #75260760

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 1e18
#define eps 1e-9
#define ls 2*k
#define rs 2*k+1
using namespace std;

const int N=3e5+5,M=1e7;
const int mod=998244353;
const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

int n;
int sum[N][3];
string s;
map<int,int>cnt1,cnt2,cnt3;
map<pair<int,int>,int>cnt;
signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int tc=1; 
    while(tc--){
    	cin>>n>>s;
    	s=" "+s;
    	int ans=n*(n+1)/2;
    	for(int i=1;i<=n;i++){
    		for(int j=0;j<3;j++)
    			sum[i][j]=sum[i-1][j];
    		if(s[i]=='A') sum[i][0]++;
    		else if(s[i]=='B') sum[i][1]++;
    		else sum[i][2]++;
		}
		int ret1=0,ret2=0,ret3=0;
		cnt1[0]=1,cnt2[0]=1,cnt3[0]=1;
		for(int i=1;i<=n;i++){
			int now1=sum[i][0]-sum[i][1],now2=sum[i][1]-sum[i][2],now3=sum[i][2]-sum[i][0];
			ret1+=cnt1[now1];
			ret2+=cnt2[now2];
			ret3+=cnt3[now3];
			cnt1[now1]++,cnt2[now2]++,cnt3[now3]++;
//			cout<<i<<' '<<ret1<<' '<<ret2<<' '<<ret3<<'\n';
		}
//		cout<<ret1<<' '<<ret2<<' '<<ret3<<'\n';
		ans=ans-ret1-ret2-ret3;
		int res=0;
		cnt[{0,0}]=1;
		for(int i=1;i<=n;i++){
			int now1=sum[i][0]-sum[i][1],now2=sum[i][1]-sum[i][2];
			res+=cnt[{now1,now2}];
			cnt[{now1,now2}]++;
		}
		ans+=res*2;
		cout<<ans<<'\n';
    }

    return 0;
}
/*
6
AABBCC

*/

Submission Info

Judge Result