verify/aoj_alds1/aoj_alds1_5_d.test.cpp

View this file on GitHub
Last update: 2024-02-18 06:04:00+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D

Depends on

Code

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

#include <bits/stdc++.h>

#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/aoj_alds1/aoj_alds1_5_d.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D"

#include <bits/stdc++.h>

#line 2 "dp/inversion_number.hpp"

#line 2 "data_structure/fenwick_tree.hpp"

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)); }
    // output
    friend std::ostream& operator<<(std::ostream& os, const FenwickTree& fen) {
        for (int i = 0; i < fen.n; i++) os << fen.get(i) << " \n"[i == fen.n - 1];
        return os;
    }
};
#line 4 "dp/inversion_number.hpp"

template <class T> long long inversion_number(std::vector<T>& A) {
    auto B = A;
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());
    int N = (int)B.size();
    FenwickTree<int> fen(N);
    long long ret = 0;
    for (auto& ai : A) {
        int i = lower_bound(B.begin(), B.end(), ai) - B.begin();
        ret += fen.sum(i + 1, N);
        fen.add(i, 1);
    }
    return ret;
}
#line 6 "verify/aoj_alds1/aoj_alds1_5_d.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;
}