HackerEarth A sorted string problem solution

In this HackerEarth A sorted string problem solution You are given a string S of length N. The string contains only ‘a’, ‘b’, and ‘c’.

Your task is to find the count of substrings in string S that have F(‘a’) > F(‘c’). Print ans%(10^9 + 7).

Here, F(x) denotes the frequency of occurrence of character x in the string.

HackerEarth A sorted string problem solution.

#include<bits/stdc++.h>
using namespace std;
#define int long long
int BIT[800000];

int query(int x)      //returns the sum of first x elements in given array a[]
{
     int sum = 0;
     for(; x > 0; x -= x&-x)
         sum += BIT[x];
     return sum;
}

void update(int x, int delta)       //add "delta" at index "x"
{
    for(; x <= 3e5; x += x&-x)
          BIT[x] += delta;
}

int solve(string s, int n)
{
    memset(BIT, 0, sizeof(BIT));

    // make binary
    int com[n+1] = {0};
    for(int i=0;i<n;i++)
    {   
        int flag = (s[i]=='a'?1:(s[i]=='b'?0:-1));
        com[i+1] = com[i] + flag;
    }
    
    // compress BIT
    map< pair<int,int>, int > dup;
    for(int i=0;i<=n;i++)
    dup[{com[i], i}] = 0;
    
    int i=1, prev = 0;
    for(auto it = dup.begin(); it != dup.end(); it++)
    {
        if(it->first.first != prev)
            i++;
        it->second = i;
        prev = it->first.first;
        // cout << it->first.first << " " << it->first.second << " " << it->second << "n";
    }
    // cout << i << "n";
    
    update(dup[{0,0}], 1);
    // BIT calls
    int ans = 0;
    for(i=1;i<=n;i++)
    {
        int z = query(dup[{com[i], i}]-1);
        ans += z;
        // cout << z << " ";
        update(dup[{com[i], i}], 1);
    }
    return ans;
}

int32_t main()
{
    int n;
    string s;
    cin >> n >> s;
    
    cout << solve(s, n);
    return 0;
}

Second solution

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

template<typename T>
struct MOS{
    tree<pair<T, int>, null_type, less<pair<T, int>>, rb_tree_tag,tree_order_statistics_node_update> os;
    map<T, int> cnt;
    int size(){
        return os.size();
    }
    int order_of_key(const T &x){
        return os.order_of_key({x, 0});
    }
    int ge(int x){
        return os.size() - order_of_key(x);
    }
    void insert(const T &x){
        os.insert({x, cnt[x]++});
    }
    void erase(const T &x){
        os.erase({x, --cnt[x]});
    }
};
typedef long long ll;
const int maxn = 1e3 + 14, mod = 1e9 + 7;

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    MOS<int> os;
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cur = 0;
    os.insert(cur);
    ll ans = 0;
    for(auto c : s){
        if(c == 'a')
            cur++;
        else if(c == 'c')
            cur--;
        ans += os.order_of_key(cur);
        os.insert(cur);
    }
    cout << ans % mod << 'n';
}