rcpl

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ruthen71/rcpl

:heavy_check_mark: verify/dp/inversion_number.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D"

#include <iostream>

#include "dp/inversion_number.hpp"

int main() {
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) std::cin >> A[i];
    std::cout << inversion_number<int>(A) << '\n';
    return 0;
}
#line 1 "verify/dp/inversion_number.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D"

#include <iostream>

#line 2 "dp/inversion_number.hpp"

#line 2 "data_structure/fenwick_tree.hpp"

#include <vector>
#include <cassert>

template <class T> struct FenwickTree {
    int n;
    std::vector<T> seg;
    FenwickTree() : n(0) {}
    FenwickTree(int n) : n(n), seg(n + 1, 0) {}
    FenwickTree(std::vector<T>& arr) {
        n = int(arr.size());
        seg.resize(n + 1);
        for (int i = 0; i < n; i++) add(i, arr[i]);
    }
    // A[i] += x
    void add(int i, const T& x) {
        assert(0 <= i and i < n);
        i++;  // 1-indexed
        while (i <= n) {
            seg[i] += x;
            i += i & -i;
        }
    }
    // A[0] + ... + A[i - 1]
    T sum(int i) const {
        assert(0 <= i and i <= n);
        T s = T(0);
        while (i > 0) {
            s += seg[i];
            i -= i & -i;
        }
        return s;
    }
    // A[a] + ... + A[b - 1]
    T sum(int a, int b) const {
        assert(0 <= a and a <= b and b <= n);
        return sum(b) - sum(a);
    }
    // return A[i]
    T get(int i) const { return sum(i, i + 1); }
    // A[i] = x
    void set(int i, const T x) { add(i, x - get(i)); }

    std::vector<T> make_vector() {
        std::vector<T> vec(n);
        for (int i = 0; i < n; i++) vec[i] = get(i);
        return vec;
    }
};
#line 4 "dp/inversion_number.hpp"
#include <algorithm>

template <class T> long long inversion_number(std::vector<T>& a) {
    auto z = a;
    std::sort(z.begin(), z.end());
    z.erase(std::unique(z.begin(), z.end()), z.end());
    const int n = (int)(z.size());
    FenwickTree<int> fen(n);
    long long ret = 0;
    for (auto& ai : a) {
        int i = lower_bound(z.begin(), z.end(), ai) - z.begin();
        ret += fen.sum(i + 1, n);
        fen.add(i, 1);
    }
    return ret;
}
#line 6 "verify/dp/inversion_number.test.cpp"

int main() {
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) std::cin >> A[i];
    std::cout << inversion_number<int>(A) << '\n';
    return 0;
}
Back to top page