#include "shoes.h" #include <iostream> #include <vector> #include <algorithm> #include <cassert> #include <cstring> #include <unordered_map> using namespace std; using ll = long long; #define FOR(i, a, b) for (int i = a; i <= b; ++i) #define FORA(i, a) for (auto &i : a) #define FORB(i, a, b) for (int i = a; i >= b; --i) ll count_swaps(vector<int> s) { int n = (int) s.size(); unordered_map<int, vector<int>> pos; FORB(i, n - 1, 0) pos[s[i]].push_back(i); vector<int> bit(n + 1, 0); ll ans = 0; FOR(i, 0, n - 1) if (s[i] < 0) { int j = pos[-s[i]].back(); pos[-s[i]].pop_back(); ans += i; for (int x = i + 1; x > 0; x -= x & (-x)) ans -= bit[x]; for (int x = i + 1; x <= n; x += x & (-x)) ++bit[x]; ans += j; for (int x = j + 1; x > 0; x -= x & (-x)) ans -= bit[x]; for (int x = j + 1; x <= n; x += x & (-x)) ++bit[x]; } return ans; }