#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define PB push_back struct segtree{ long long dd, htt, mid, val; segtree *L, *R; segtree(int l, int r){ //cout<<l<<" "<<r<<endl; htt=r; dd=l; val=0; mid=(htt+dd)/2; if(l!=r){ L=new segtree(l, mid); R=new segtree(mid+1, r); val=L->val+R->val; }else{ val=1; } } void update(int ps){ if(dd==htt){ val=0; //cout<<ps<<endl; return ; } if(ps<=mid){ L->update(ps); }else{ R->update(ps); } val=L->val+R->val; } long long query(int l, int r){ if(dd==l&&r==htt){ return val; } else if(r<=mid)return L->query(l, r); else if(l>mid)return R->query(l, r); else return L->query(l, mid)+R->query(mid+1, r); } }; long long count_swaps(std::vector<int> s) { long long n = s.size()/2, sum=0; /* for(int i = 0 ; i < n ; i++){ sum+=i; }*/ vector<int>pos[n*2+1]; int conut[n*2+1]; memset(conut, -1, sizeof conut); //bool contado[n*2+1]; for(int i = 0 ; i < n * 2 ; i++){ //contado[abs(s[i])*2]=false; if(s[i]>0){//par pos[s[i]*2].PB(i); if(conut[s[i]*2]==-1)conut[s[i]*2]=0; }else{ pos[(-s[i]*2)-1].PB(i); if(conut[-s[i]*2-1]==-1)conut[(-s[i]*2)-1]=0; } } segtree *tree = new segtree(0, n*2); for(int i = 0 ; i < n*2 ; i++){ if(s[i]>0){ conut[s[i]*2]++; s[pos[s[i]*2-1][conut[s[i]*2-1]]]=0; //cout<<i<<" "<<pos[s[i]*2-1][conut[s[i]*2-1]]<<" = "<<tree->query(i, pos[s[i]*2-1][conut[s[i]*2-1]])<<endl; sum+=tree->query(i, pos[s[i]*2-1][conut[s[i]*2-1]])-1; tree->update(pos[s[i]*2-1][conut[s[i]*2-1]]); //cout<<'s'<<sum<<endl; conut[s[i]*2-1]++; }else if(s[i]<0){ conut[-s[i]*2-1]++; s[pos[-s[i]*2][conut[-s[i]*2]]]=0; if(i+1<pos[-s[i]*2][conut[-s[i]*2]])sum+=tree->query(i+1, pos[-s[i]*2][conut[-s[i]*2]])-1; tree->update(pos[-s[i]*2][conut[-s[i]*2]]); conut[-s[i]*2]++; //cout<<'s'<<sum<<endl; } } return sum; }