Guest User

Untitled

a guest
Nov 2nd, 2020
150
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // #define _CRT_SECURE_NO_WARNINGS
  2. // ░░░░░░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░░░░░
  3. // ░░░░░░█░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░█░░░░░
  4. // ░░░░░░█░█░▀░░░░░▀░░▀░░░░█░█░░░░░
  5. // ░░░░░░█░█░░░░░░░░▄▀▀▄░▀░█░█▄▀▀▄░
  6. // █▀▀█▄░█░█░░▀░░░░░█░░░▀▄▄█▄▀░░░█░
  7. // ▀▄▄░▀██░█▄░▀░░░▄▄▀░░░░░░░░░░░░▀▄
  8. // ░░▀█▄▄█░█░░░░▄░░█░░░▄█░░░▄░▄█░░█
  9. // ░░░░░▀█░▀▄▀░░░░░█░██░▄░░▄░░▄░███
  10. // ░░░░░▄█▄░░▀▀▀▀▀▀▀▀▄░░▀▀▀▀▀▀▀░▄▀░
  11. // ░░░░█░░▄█▀█▀▀█▀▀▀▀▀▀█▀▀█▀█▀▀█░░░
  12. // ░░░░▀▀▀▀░░▀▀▀░░░░░░░░▀▀▀░░▀▀░░░░
  13. #include <algorithm>
  14. #include <array>
  15. #include <bitset>
  16. #include <chrono>
  17. #include <cmath>
  18. #include <cstdio>
  19. #include <cstring>
  20. #include <ctime>
  21. #include <deque>
  22. #include <fstream>
  23. #include <iostream>
  24. #include <map>
  25. #include <queue>
  26. #include <random>
  27. #include <set>
  28. #include <stack>
  29. #include <string>
  30. #include <unordered_map>
  31. #include <unordered_set>
  32. #include <vector>
  33. #pragma GCC optimize("Ofast,inline,unroll-loops,no-stack-protector")
  34. using namespace std;
  35. #define rep(i, a, n) for (int i = a; i < n; i++)
  36. #define per(i, a, n) for (int i = n - 1; i >= a; i--)
  37. #define all(v) v.begin(), v.end()
  38. //#define sz(v) ((int)(v).size())
  39. //#define trav(a, x) for (auto& a: x)
  40. typedef long long ll;
  41. typedef double db;
  42. typedef long double ld;
  43. typedef unsigned int uint;
  44. typedef unsigned long long ull;
  45. //typedef string str;
  46. typedef vector<int> vi;
  47. const int INF = 1e9 + 7;
  48. const int MOD = 1e9 + 7;
  49. const int di[4] = { 1, 0, -1, 0 };
  50. const int dj[4] = { 0, 1 ,0, -1 };
  51. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  52.  
  53. ll t[800000];
  54.  
  55. void change(int v, int l, int r, int pos) {
  56. if (r - l == 1) {
  57. t[v]++;
  58. return;
  59. }
  60. int m = (l + r) / 2;
  61. if (pos < m) {
  62. change(2 * v + 1, l, m, pos);
  63. }
  64. else {
  65. change(2 * v + 2, m, r, pos);
  66. }
  67. t[v] = t[2 * v + 1] + t[2 * v + 2];
  68. }
  69.  
  70. ll asksum(int v, int l, int r, int askl, int askr) {
  71. if (r <= askl || l >= askr) {
  72. return 0;
  73. }
  74. if (l >= askl && r <= askr) {
  75. return t[v];
  76. }
  77. int m = (l + r) / 2;
  78. return asksum(2 * v + 1, l, m, askl, askr) + asksum(2 * v + 2, m, r, askl, askr);
  79. }
  80.  
  81. int main() {
  82. ios_base::sync_with_stdio(0);
  83. cin.tie(0);
  84. cout.tie(0);
  85. int n;
  86. cin >> n;
  87. string s;
  88. cin >> s;
  89. string rs = s;
  90. reverse(all(rs));
  91. vector<vector<int>>m(26);
  92. vector<int>p(n);
  93. for (int i = 0; i < n; i++) {
  94. m[s[i] - 'a'].push_back(i);
  95. }
  96. for(int i = n - 1; i >= 0; i--){
  97. p[m[rs[i] - 'a'].back()] = i;
  98. m[rs[i] - 'a'].pop_back();
  99. }
  100. ll answ = 0;
  101. for (int i = 0; i < n; i++) {
  102. answ += asksum(0, 0, n, p[i] + 1, n);
  103. change(0, 0, n, p[i]);
  104. }
  105. cout << answ << endl;
  106. }
RAW Paste Data