#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 lazy[4 * N], seg[4 * N]; void push(int l, int r, int i){ seg[i] += lazy[i] * (r - l + 1); if (l != r) lazy[2 * i] += lazy[i], lazy[2 * i + 1] += lazy[i]; lazy[i] = 0; } void update(int l, int r, int i, int ll, int rr, int val){ push(l, r, i); if (l >= ll && r <= rr) { lazy[i] += val; push(l, r, i); return; } if (r < ll || l > rr) return; int mid = (l + r) / 2; update(l, mid, 2 * i, ll, rr, val); update(mid + 1, r, 2 * i + 1, ll, rr, val); seg[i] = seg[2 * i] + seg[2 * i + 1]; } int query(int l, int r, int i, int ll, int rr){ push(l, r, i); 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); } } seg; lll count_swaps(vector<int> a) { int n = a.size()/2; reverse(all(a)); a.emb(0); reverse(all(a)); lll ans = 0; map <int, set <int>> mp; for (int i = 1; i <= 2*n; i++) mp[a[i]].em(i); for (int i = 1; i <= 2*n; i++) { if (i % 2 == 0) continue; int idx = i - seg.query(1, 2*n, 1, i, i); int cur = *mp[a[idx] * -1].begin(); // cout << i << ": " << cur << "\n"; mp[a[idx] * -1].erase(cur); mp[a[idx]].erase(idx); cur += seg.query(1, 2*n, 1, cur, cur); int cnt = 0; if (a[idx] < 0) cnt = cur - i - 1; else cnt += cur - i; ans += cnt; // cout << i << ": " << "[" << idx << ", " << cur << "] : " << cnt << "\n"; seg.update(1, 2*n, 1, idx, cur, 1); // for (auto e : a) cout << e << " "; cout << " : " << cnt << "\n"; } return ans; } /* sub3: find closest position sub4: -1 1 : 0 -1 -2 1 2 : 1 -1 -2 -3 1 2 3 : 3 ans = n(n-1)/2 sub5: n^2 for each idx i: find closest left/right shoe then just count number of swaps, then change index of other shoes accordingly..? _,_,_,X,_,_,Y,_,X,_,_,Y -3 2 1 -2 3 1 3 2 1 -2 -3 -1 -3 3 2 1 -2 -1: 4 : [3, 5] idx -1 -3 3 -2 2 1 -1: 2 : [5, 5] idx -1 -3 3 -2 2 -1 1: 1 : no change [-2, 1, -2, 2, -1, 2] [-2, 2, 1, -2, -1, 2] : 2 [-2, 2, -1, 1, -2, 2] : 2 */