Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define pll pair<ll, ll>
- #define fi first
- #define se second
- #define pb push_back
- #define task "XMAX"
- #define pii pair<ll, pll>
- using namespace std;
- using ll = long long;
- const int N = 2e5+5;
- const ll mod = 1e9+7;
- const ll base = 350;
- const ll cs = 331;
- ll m, n, t, k, tong, q, ans, a[N], b[N], c[N], fe[N];
- vector<ll> adj[N], kq;
- string s;
- void add(ll id)
- {
- for(; id <= n; id += id & -id)++fe[id];
- }
- ll get(ll id)
- {
- ll total = 0;
- for(; id; id -= id & -id)total += fe[id];
- return total;
- }
- ll pw(ll k, ll n)
- {
- ll total = 1;
- for(; n; n >>= 1)
- {
- if(n & 1)total = total * k % mod;
- k = k * k % mod;
- }
- return total;
- }
- bool cmp(const ll& x, const ll& y)
- {
- return a[x] < a[y];
- }
- void sol()
- {
- cin >> n >> s;
- for(int i = 0; i < n; i ++)
- {
- k = s[i] - 'a';
- adj[k].pb(i+1);
- }
- for(int i = 0; i < 26; i ++)reverse(adj[i].begin(), adj[i].end());
- reverse(s.begin(), s.end());
- for(int i = 0; i < n; i ++)
- {
- int j = s[i] - 'a';
- k = adj[j].back();
- //cout << k <<" ";
- adj[j].pop_back();
- ans += get(n) - get(k);
- add(k);
- }
- cout << ans;
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if(fopen(task".inp", "r"))
- {
- freopen(task".inp", "r", stdin);
- freopen(task".out", "w", stdout);
- }
- int ntest = 1;
- //cin >> ntest;
- while(ntest -- > 0)
- sol();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement