#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;
const int MAXN = 2e5+10;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
int N;
ll tree[MAXN];
void upd(int p){ for(;p<=2*N;p+=(p&-p)) tree[p]++; }
ll query(int p){
ll ret=0;
for(;p>0;p-=(p&-p)) ret+=tree[p];
return ret;
}
void coordinateCompression(vector<int>& arr){
vector<int> proc;
for(auto u : arr) proc.pb(abs(u));
sort(all(proc));
proc.erase(unique(all(proc)), proc.end());
map<int, int> comp;
for(int i=0;i<(int)proc.size();i++) comp[proc[i]]=i+1;
for(auto& u : arr){
if(u<0) u=-comp[-u];
else u=comp[u];
}
}
ll count_swaps(vector<int> s) {
N=((int)s.size())>>1;
coordinateCompression(s);
vector<queue<int>> occ(N+1), aux(N+1);
vector<int> left;
for(int i=0;i<2*N;i++){
if(s[i]>0) occ[s[i]].push(i+1), aux[s[i]].push(i+1);
else left.pb(i+1);
}
vector<pii> proc;
for(auto u : left){
int id=-s[u-1];
proc.pb({u+aux[id].front(), u});
aux[id].pop();
}
left.clear();
sort(all(proc));
for(auto [u, v]: proc) left.pb(v);
ll ans=0;
for(int i=0;i<N;i++){
ll curr=left[i]-query(left[i])-1;
upd(left[i]);
int id=abs(s[left[i]-1]);
curr+=occ[id].front()-query(occ[id].front())-1;
upd(occ[id].front());
occ[id].pop();
ans+=curr;
}
return ans;
}
Compilation message
rect.cpp:1:10: fatal error: shoes.h: No such file or directory
1 | #include "shoes.h"
| ^~~~~~~~~
compilation terminated.
