#include "shoes.h" #include "bits/stdc++.h" using namespace std; const int N = 1e5 + 5; int len; deque < int > b[N]; map < int , int > cnt[N]; void upd(int l, int r){ int ll = l / len, rr = r / len; if(ll == rr){ deque < int > d; for(int i = l % len; i <= r % len; i++) d.push_back(b[ll][i]); d.push_front(d.back()); d.pop_back(); int idx = 0; for(int i = l % len; i <= r % len; i++) b[ll][i] = d[idx++]; return; } deque < int > x = {b[rr][r % len]}; for(int i = l % len; i < len; i++){ x.push_back(b[ll][i]); } int _idx = 0; for(int i = l % len; i < len; i++){ b[ll][i] = x[_idx++]; } int lst = x.back(); cnt[ll][x.front()]++; cnt[ll][lst]--; for(int i = ll + 1; i <= rr - 1; i++){ b[i].push_front(lst); cnt[i][lst]++; lst = b[i].back(); b[i].pop_back(); cnt[i][lst]--; } deque < int > y = {lst}; for(int i = 0; i <= r % len; i++){ y.push_back(b[rr][i]); } int idx_ = 0; for(int i = 0; i <= r % len; i++){ b[rr][i] = y[idx_++]; } } int ask(int l, int r, int x){ int ll = l / len, rr = r / len; if(ll == rr){ for(int i = l % len; i <= r % len; i++){ if(b[ll][i] == x){ return ll * len + l; } } return l; } for(int i = l % len; i < len; i++){ if(b[ll][i] == x){ return ll * len + i; } } int idx = -1; for(int i = ll + 1; i <= rr - 1; i++){ if(cnt[i][x] > 0){ idx = i; break; } } if(idx != -1){ for(int i = 0; i < len; i++){ if(b[idx][i] == x){ return idx * len + i; } } } for(int i = 0; i <= r % len; i++){ if(b[rr][i] == x){ return rr * len + i; } } return l; } long long count_swaps(vector < int > s){ int n = s.size(); len = sqrt(n + .0) + 1; for(int i = 0; i < n; i++){ b[i / len].push_back(s[i]); cnt[i / len][s[i]]++; } long long ans = 0; for(int i = 0; i < n; i++){ int si = b[i / len][i % len], si_ = si; if(i >= 1) si_ = b[(i - 1) / len][(i - 1) % len]; if(si > 0 && i % 2 == 0){ int j = ask(i, n - 1, -si); ans += (j - (i + 1) + 1); // cout << i << '-' << j << endl; upd(i, j); } else if(si < 0 && i % 2 == 1 || si > 0 && si != -si_){ int j = ask(i, n - 1, -si_); ans += (j - (i + 1) + 1); // cout << i << '-' << j << endl; upd(i, j); } // for(int _ = 0; _ < len; _++){ // for(auto __ : b[_])cout << __ << ' '; // } // cout << endl; } return ans; }