verify/aoj/aoj_alds1_5_d.test.cpp

View this file on GitHub
Last update: 2025-02-27 06:13:46+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 <bits/stdc++.h>
using namespace std;

#include "../../math/inversion_number.hpp"

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

    cout << inversion_number<int>(A) << endl;
    

    return 0;
}

#line 1 "verify/aoj/aoj_alds1_5_d.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_5_D"

#include <bits/stdc++.h>
using namespace std;

#line 1 "data_structure/fenwick_tree.hpp"
template <typename T=int>
struct FenwickTree {
    int n;
    vector<T> data;
    FenwickTree(int n) : n(n), data(n, 0) {}

    void add(int p, T x) {
        for(p++; p <= n; p += p & -p) data[p - 1] += x;
    }

    T sum(int r) {
        T s = 0;
        for(; r; r -= r & -r) s += data[r - 1];
        return s;
    }
    
    T sum(int l, int r) {
        return sum(r) - sum(l);
    }
};
#line 2 "math/inversion_number.hpp"

template<typename T>
long long inversion_number(const vector<T>& A) {
    vector<T> B = A;
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());

    FenwickTree<T> bit(B.size());

    long long ret = 0;
    for(int i = 0; i < (int)A.size(); i++) {
        int rank = lower_bound(B.begin(), B.end(), A[i]) - B.begin() + 1;
        ret += i - bit.sum(rank);
        bit.add(rank, 1);
    }
    return ret;
}
#line 7 "verify/aoj/aoj_alds1_5_d.test.cpp"

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

    cout << inversion_number<int>(A) << endl;
    

    return 0;
}