転倒数

ten(v)に入れたら勝手に座標圧縮されて転倒数が帰ってくる

セグ木が一緒についてきてるのでセグ木を別で定義してる場合は気を付ける

転倒数 = 自分よりも左にあるのに自分よりも大きい要素の数の総和

配列の長さをNとした時 NlogN

class st{
public:
    long long siz = 1;
    vector<long long> v;
    st (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,0);
    }
    void plus(long long i){
        i += siz;
        v[i]++;
        while(i > 1){
            i /= 2;
            v[i] = v[i*2]+v[i*2+1];
        }
    } 
    long long query(long long l,long long r){
        return query(l,r,1,0,siz-1);
    }
    private : 
    long long query(long long L,long long R,long long s,long long l,long long r){
        long long ans = 0;
        if(l >= L && r <= R){
            ans += v[s];
            return ans;
        }
        if(r < L || l > R)return 0;
        ans += query(L,R,s*2,l,(l+r)/2);
        ans += query(L,R,s*2+1,(l+r)/2+1,r);
        return ans;
    }
};

long long ten(vector<long long> v){
    long long n = v.size();
    vector<long long> sorted = v;
    sort(sorted.begin(),sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    st seg(sorted.size());
    long long ans = 0;
    for(long long i = 0;i < n;i++){
        long long pos = lower_bound(sorted.begin(),sorted.end(),v[i])-sorted.begin();
        ans += seg.query(pos+1,sorted.size()-1);
        seg.plus(pos);
    }
    return ans;
}

逆転倒数

自分よりも左にあって自分よりも小さい要素の数の総和を計算する

配列の長さをNとした時 NlogN

class st{
public:
    long long siz = 1;
    vector<long long> v;
    st (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,0);
    }
    void plus(long long i){
        i += siz;
        v[i]++;
        while(i > 1){
            i /= 2;
            v[i] = v[i*2]+v[i*2+1];
        }
    } 
    long long query(long long l,long long r){
        return query(l,r,1,0,siz-1);
    }
    private : 
    long long query(long long L,long long R,long long s,long long l,long long r){
        long long ans = 0;
        if(l >= L && r <= R){
            ans += v[s];
            return ans;
        }
        if(r < L || l > R)return 0;
        ans += query(L,R,s*2,l,(l+r)/2);
        ans += query(L,R,s*2+1,(l+r)/2+1,r);
        return ans;
    }
};
long long ten(vector<long long> v){
    long long n = v.size();
    vector<long long> sorted = v;
    sort(sorted.begin(),sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    st seg(sorted.size());
    long long ans = 0;
    for(long long i = 0;i < n;i++){
        long long pos = lower_bound(sorted.begin(),sorted.end(),v[i])-sorted.begin();
        ans += seg.query(0,pos-1);
        seg.plus(pos);
    }
    return ans;
}