#include "shoes.h" #include <bits/stdc++.h> #define lll long long #define emb emplace_back #define em emplace #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define pii pair <int, int> using namespace std; const int N = 2e5 + 5; struct { int seg[4 * N]; void update(int l, int r, int i, int idx, int val){ if (l == r) return seg[i] = val, void(); int mid = (l + r) / 2; if (idx <= mid) update(l, mid, 2 * i, idx, val); else update(mid + 1, r, 2 * i + 1, idx, val); seg[i] = seg[2 * i] + seg[2 * i + 1]; } int query(int l, int r, int i, int ll, int rr){ if (l >= ll && r <= rr) return seg[i]; if (r < ll || l > rr) return 0; int mid = (l + r) / 2; return query(l, mid, 2 * i, ll, rr) + query(mid + 1, r, 2 * i + 1, ll, rr); } int search(int l, int r, int i, int k){ if (l == r) return l; int mid = (l + r) / 2; if (seg[2 * i] >= k) return search(l, mid, 2 * i, k); else return search(mid + 1, r, 2 * i + 1, k - seg[2 * i]); } } seg; lll count_swaps(vector<int> a) { memset(seg.seg, 0, sizeof seg.seg); int n = a.size()/2; reverse(all(a)); a.emb(0); reverse(all(a)); map <int, set <int>> mp; for (int i = 1; i <= 2*n; i++) { mp[a[i]].em(i); seg.update(1, 2*n, 1, i, 1); } // for (int i = 1; i <= 2 * n; i++) cout << seg.query(1, 2*n, 1, i, i) << " "; cout << "\n"; lll ans = 0; for (int i = 1; i <= 2*n; i++) { if (i % 2 == 0) continue; int idx = seg.search(1, 2*n, 1, 1); int val = a[idx]; int nxt = *mp[val * -1].begin(); mp[val].erase(idx); mp[val * -1].erase(nxt); ans += seg.query(1, 2*n, 1, idx, nxt) - 1 - (val < 0); // cout << i << ": " << val << "\n"; // cout << "[" << idx << ", " << nxt << "]\n"; // cout << "ANS FOR " << i << " : " << seg.query(1, 2*n, 1, idx, nxt) - 1 - (val < 0) << "\n"; seg.update(1, 2*n, 1, idx, 0); seg.update(1, 2*n, 1, nxt, 0); // for (int j = 1; j <= 2*n; j++) { // cout << seg.query(1, 2*n, 1, i, i) << " "; // } // cout << "\n"; // cout << "-------------\n"; } return ans; } /* OMG OBSERVE ORK LAEW */