Submission #72530359

---

Source Code Expand

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn = 5e5 + 5;
int a[maxn];
class BIT //树状数组
{
public:
    long long tr[maxn*2+100];
    int n;

    void init(int x) //清空并初始化
    {
        for (int i = 1; i <= x; i++)
            tr[i] = 0;
        n = x;
    }

    int lowbit(int x)
    {
        return x & -x;
    }

    void add(int x, long long d) //将第x个数+k
    {
        for (int i = x; i <= n; i += lowbit(i))
            tr[i] += d;
    }

    long long sum(int x) //求前x个数的和
    {
        long long ans = 0;
        for (int i = x; i; i -= lowbit(i))
            ans += tr[i];
        return ans;
    }
} tr;
int sum[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin>>n;
    string s;
    cin>>s;
    s=' '+s;
    long long ans=0;
    sum[0]=n+2;
    tr.n=2*n+10;
    tr.add(sum[0],1);
    for (int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1];
        if (s[i]=='A')
            sum[i]++;
        else if (s[i]=='B')
            sum[i]--;
        ans+=tr.sum(sum[i]-1);
        tr.add(sum[i],1);
    }
    cout<<ans;
}

Submission Info

Judge Result