Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // #define _CRT_SECURE_NO_WARNINGS
- // ░░░░░░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░░░░░
- // ░░░░░░█░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░█░░░░░
- // ░░░░░░█░█░▀░░░░░▀░░▀░░░░█░█░░░░░
- // ░░░░░░█░█░░░░░░░░▄▀▀▄░▀░█░█▄▀▀▄░
- // █▀▀█▄░█░█░░▀░░░░░█░░░▀▄▄█▄▀░░░█░
- // ▀▄▄░▀██░█▄░▀░░░▄▄▀░░░░░░░░░░░░▀▄
- // ░░▀█▄▄█░█░░░░▄░░█░░░▄█░░░▄░▄█░░█
- // ░░░░░▀█░▀▄▀░░░░░█░██░▄░░▄░░▄░███
- // ░░░░░▄█▄░░▀▀▀▀▀▀▀▀▄░░▀▀▀▀▀▀▀░▄▀░
- // ░░░░█░░▄█▀█▀▀█▀▀▀▀▀▀█▀▀█▀█▀▀█░░░
- // ░░░░▀▀▀▀░░▀▀▀░░░░░░░░▀▀▀░░▀▀░░░░
- #include <algorithm>
- #include <array>
- #include <bitset>
- #include <chrono>
- #include <cmath>
- #include <cstdio>
- #include <cstring>
- #include <ctime>
- #include <deque>
- #include <fstream>
- #include <iostream>
- #include <map>
- #include <queue>
- #include <random>
- #include <set>
- #include <stack>
- #include <string>
- #include <unordered_map>
- #include <unordered_set>
- #include <vector>
- #pragma GCC optimize("Ofast,inline,unroll-loops,no-stack-protector")
- using namespace std;
- #define rep(i, a, n) for (int i = a; i < n; i++)
- #define per(i, a, n) for (int i = n - 1; i >= a; i--)
- #define all(v) v.begin(), v.end()
- //#define sz(v) ((int)(v).size())
- //#define trav(a, x) for (auto& a: x)
- typedef long long ll;
- typedef double db;
- typedef long double ld;
- typedef unsigned int uint;
- typedef unsigned long long ull;
- //typedef string str;
- typedef vector<int> vi;
- const int INF = 1e9 + 7;
- const int MOD = 1e9 + 7;
- const int di[4] = { 1, 0, -1, 0 };
- const int dj[4] = { 0, 1 ,0, -1 };
- mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
- ll t[800000];
- void change(int v, int l, int r, int pos) {
- if (r - l == 1) {
- t[v]++;
- return;
- }
- int m = (l + r) / 2;
- if (pos < m) {
- change(2 * v + 1, l, m, pos);
- }
- else {
- change(2 * v + 2, m, r, pos);
- }
- t[v] = t[2 * v + 1] + t[2 * v + 2];
- }
- ll asksum(int v, int l, int r, int askl, int askr) {
- if (r <= askl || l >= askr) {
- return 0;
- }
- if (l >= askl && r <= askr) {
- return t[v];
- }
- int m = (l + r) / 2;
- return asksum(2 * v + 1, l, m, askl, askr) + asksum(2 * v + 2, m, r, askl, askr);
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin >> n;
- string s;
- cin >> s;
- string rs = s;
- reverse(all(rs));
- vector<vector<int>>m(26);
- vector<int>p(n);
- for (int i = 0; i < n; i++) {
- m[s[i] - 'a'].push_back(i);
- }
- for(int i = n - 1; i >= 0; i--){
- p[m[rs[i] - 'a'].back()] = i;
- m[rs[i] - 'a'].pop_back();
- }
- ll answ = 0;
- for (int i = 0; i < n; i++) {
- answ += asksum(0, 0, n, p[i] + 1, n);
- change(0, 0, n, p[i]);
- }
- cout << answ << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement