1430E - String Reversal - CodeForces Solution

#include <bits/stdc++.h>
# define int long long
# define fir first
# define sec second
# define pb push_back
using namespace std;

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

int posi[cnst*4];
int arr[cnst];

int build(int a, int b, int id) {
    if(a == b) return posi[id] = arr[a];
    int mid = (a+b)/2;
    return posi[id] = build(a, mid, id*2)+build(mid+1, b, id*2+1);
}

void update(int a, int b, int id, int pos, int val) {
    if(a == pos && b == pos) {
        posi[id] = val;
        return;
    }
    int mid =(a+b)/2;
    if(pos <= mid) update(a, mid, id*2, pos, val);
    else update(mid+1, b, id*2+1, pos, val);
    posi[id] = posi[id*2]+posi[id*2+1];
}

int get(int a, int b, int id, int from, int to) {
    if(to < a || from > b) return 0;
    if(from <= a && b <= to) return posi[id];
    int mid = (a+b)/2;
    return get(a, mid, id*2, from, to)+get(mid+1, b, id*2+1, from, to);
}


void solve() {
    int n; cin >> n;
    string s; cin >> s;

    int fre[30];
    int ans = 0;
    vector<int> pos[30];
    memset(fre, 0, sizeof(fre));

    for(int i = 0; i<n; i++) {
        int x = s[i]-'a'+1;
        pos[x].pb(i+1);
        update(1, n, 1, i+1, 1);
    }

    for(int i = 1; i<=n; i++) {
        int x = s[(n-i)]-'a'+1;
        ans += get(1, n, 1, 1, pos[x][fre[x]]-1);
        update(1, n, 1, pos[x][fre[x]], 0);
        fre[x]++;
        // cerr << x << " " << pos[x][fre[x]] << endl;
        // cerr << i << " " << ans << endl;
    }

    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

//2