#include "shoes.h" #include <bits/stdc++.h> #define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define endl "\n" #define ff first #define ss second #define pb push_back #define all(v) v.begin(), v.end() using namespace std; struct BIT{ int n; vector <int> t; void init(int n1) { n = n1; t.assign(n+1, 0); } int find(int l, int r) { if (l > r) return 0; if (l != 1) return find(1, r) - find(1, l-1); int res=0; while (r >= 1) { res += t[r]; r -= (r & (-r)); } return res; } void update(int i, int x) { while (i <= n) { t[i] += x; i += (i & (-i)); } } int get(int l) { l++; return find(1, l); } void upd(int l, int r) { l++, r++; update(l, 1); if (r < n) update(r+1, -1); } }; long long count_swaps(vector<int> v) { int n = v.size(); vector <int> s; for (int i = 0; i < n; i++) { if (v[i] < 0) s.pb(v[i]), s.pb(-v[i]); } // for (int &i : s) cout << i << ' '; cout << endl; vector <pair<int, int>> a, b; for (int i = 0; i < n; i++) { a.pb({v[i], i}); b.pb({s[i], i}); } sort(all(a)); sort(all(b)); vector <int> pos(n); for (int i = 0; i < n; i++) pos[b[i].ss] = a[i].ss; // for (int &i : pos) cout << i << ' '; cout << endl; long long res=0; BIT t; t.init(n); for (int i = 0; i < n; i++) { int id = pos[i] + t.get(pos[i]); // cout << t.get(pos[i]) << ' '; if (i > id) continue; res += id - i; t.upd(i, id); } // cout << endl; return res; }