Submission #72543169

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,sum[N*2];
long long ans;
string s;
struct BIT{
	int tr[N*2];
	inline int lowbit(int x){return x&-x;}
	inline void add(int x){
		for(;x<=n*2;x+=lowbit(x))tr[x]++;
	}
	inline int query(int x){
		int res=0;
		for(;x;x-=lowbit(x))res+=tr[x];
		return res;
	}
}bit;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>s;
	s=" "+s;
	for(int i=1;i<=n;i++){
		if(s[i]=='A')sum[i]=sum[i-1]+1;
		else if(s[i]=='B')sum[i]=sum[i-1]-1;
		else sum[i]=sum[i-1];
	}
	bit.add(n+1);
	for(int i=1;i<=n;i++){
		ans+=bit.query(sum[i]+n);
		bit.add(sum[i]+n+1);
	}
	cout<<ans<<'\n';
	return 0;
}

Submission Info

Judge Result