test/inv_num.test.cpp

View this file on GitHub
Last update: 2024-03-03 06:51:22+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_5_D

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_5_D"
#include <iostream>
#include "C++/math/inverse_num.hpp"
int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for(auto &el: a) {
        std::cin >> el;
    }
    std::cout << inv_num(a) << '\n';
}

#line 1 "test/inv_num.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_5_D"
#include <iostream>
#line 2 "C++/math/inverse_num.hpp"

#include <algorithm>
#line 2 "C++/ds/fwtree/FenwickTree.hpp"

#include <vector>

template <class T> struct FenwickTree {
private:
    int n;
    std::vector<T> data;
    void init(const size_t size) {
        n = size + 2;
        data.resize(n + 1);
    }
public:
    FenwickTree(){}
    FenwickTree(const size_t size){ init(size); }
    FenwickTree(const std::vector<T> &a) {
        init(a.size());
        for(size_t i = 0; i < a.size(); ++i) {
            add(i, a[i]);
        }
    }
    T sum(int k) const {
        if(k < 0) {
            return 0;
        }
        T ret = 0;
        for(++k; k > 0; k -= k & -k) {
            ret += data[k];
        }
        return ret;
    }
    inline T sum(int l, int r) const { return sum(r) - sum(l - 1); }
    inline T operator[](int k) const { return sum(k) - sum(k - 1); }
    void add(int k, const T &x) {
        for(++k; k < n; k += k & -k) {
            data[k] += x;
        }
    }
    void add(const int l, const int r, const T& x) {
        add(l, x);
        add(r + 1, -x);
    }
    int lower_bound(T w) {
        if(w <= 0) {
            return 0;
        }
        int x = 0;
        for(int k = 1 << std::__lg(n); k; k >>= 1) {
            if(x + k <= n - 1 && data[x + k] < w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }
    int upper_bound(T w) {
        if(w < 0) {
            return 0;
        }
        int x = 0;
        for(int k = 1 << std::__lg(n); k; k >>= 1) {
            if(x + k <= n - 1 && data[x + k] <= w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }
};

/**
 * @brief Binary Indexed Tree
 * @see https://nyaannyaan.github.io/library/data-structure/binary-indexed-tree.hpp
 */
#line 5 "C++/math/inverse_num.hpp"
template <class T> inline long long inv_num(const std::vector<T> &a) {
    std::vector<std::pair<T, int>> p(a.size());
    for(size_t i = 0; i < a.size(); ++i) {
        p[i] = {a[i], i};
    }
    std::sort(p.begin(), p.end());
    std::vector<int> id(a.size());
    for(size_t i = 0; i < a.size(); ++i) {
        id[p[i].second] = i;
    }
    FenwickTree<T> bit(a.size());
    long long res = 0;
    for(size_t i = 0; i < a.size(); ++i) {
        res += i - bit.sum(id[i]);
        bit.add(id[i], 1);
    }
    return res;
}

/**
 * @brief 転倒数
 */
#line 4 "test/inv_num.test.cpp"
int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for(auto &el: a) {
        std::cin >> el;
    }
    std::cout << inv_num(a) << '\n';
}