Advertisement
Dang_Quan_10_Tin

XMAX

Jun 25th, 2022
681
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None
  1. #include<bits/stdc++.h>
  2. #define pll pair<ll, ll>
  3. #define fi first
  4. #define se second
  5. #define pb push_back
  6. #define task "XMAX"
  7. #define pii pair<ll, pll>
  8. using namespace std;
  9. using ll = long long;
  10. const int  N = 2e5+5;
  11. const ll mod = 1e9+7;
  12. const ll base = 350;
  13. const ll cs = 331;
  14. ll m, n, t, k, tong, q, ans, a[N], b[N], c[N], fe[N];
  15. vector<ll> adj[N], kq;
  16. string s;
  17. void add(ll id)
  18. {
  19.     for(; id <= n; id += id & -id)++fe[id];
  20. }
  21. ll get(ll id)
  22. {
  23.     ll total = 0;
  24.     for(; id; id -= id & -id)total += fe[id];
  25.     return total;
  26. }
  27. ll pw(ll k, ll n)
  28. {
  29.     ll total = 1;
  30.     for(; n; n >>= 1)
  31.     {
  32.         if(n & 1)total = total * k % mod;
  33.         k = k * k % mod;
  34.     }
  35.     return total;
  36. }
  37. bool cmp(const ll& x, const ll& y)
  38. {
  39.     return a[x] < a[y];
  40. }
  41. void sol()
  42. {
  43.  
  44.     cin >> n >> s;
  45.     for(int i = 0; i < n; i ++)
  46.     {
  47.         k = s[i] - 'a';
  48.         adj[k].pb(i+1);
  49.     }
  50.     for(int i = 0; i < 26; i ++)reverse(adj[i].begin(), adj[i].end());
  51.     reverse(s.begin(), s.end());
  52.     for(int i = 0; i < n; i ++)
  53.     {
  54.         int j = s[i] - 'a';
  55.         k = adj[j].back();
  56.         //cout << k <<" ";
  57.         adj[j].pop_back();
  58.         ans += get(n) - get(k);
  59.         add(k);
  60.     }
  61.     cout << ans;
  62. }
  63. int main()
  64. {
  65.     ios_base::sync_with_stdio(0);
  66.     cin.tie(0);
  67.     cout.tie(0);
  68.     if(fopen(task".inp", "r"))
  69.     {
  70.         freopen(task".inp", "r", stdin);
  71.         freopen(task".out", "w", stdout);
  72.     }
  73.     int ntest = 1;
  74.     //cin >> ntest;
  75.     while(ntest -- > 0)
  76.     sol();
  77. }
  78.  
Advertisement
RAW Paste Data Copied
Advertisement