#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) { memset(seg.lazy, 0, sizeof seg.lazy); memset(seg.seg, 0, sizeof seg.seg); 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); vector <int> used(2*n+1); int usecnt = 0; for (int i = 1; i <= 2*n; i++) { if (i % 2 == 0) { usecnt += used[i]; continue; } int idx = i - seg.query(1, 2*n, 1, i, i) - usecnt; // cout << i << ": VAL: " << a[idx] << "\n"; int cur = *(mp[a[idx] * -1].upper_bound(idx)); int startcur = cur; mp[a[idx] * -1].erase(cur); // cout << "STARTING_CUR: " << cur << "\n"; cur += seg.query(1, 2*n, 1, cur, cur); mp[a[idx]].erase(idx); int cnt = 0; if (a[idx] < 0) cnt = cur - i - 1; else cnt = cur - i; ans += cnt; // cout << i << ": CUR: " << cur << "\n"; // cout << i << ": " << "[" << idx << ", " << cur << "] : " << cnt << "\n"; seg.update(1, 2*n, 1, i, cur, 1); if (cur != i + 1) used[cur]++; usecnt += used[i]; // cout << "-----------------\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 3 2 1 -2 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 */