test/Inversion.test.cpp

• View this file on GitHub
• Last update: 2021-04-06 14:30:27+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_5_D

Depends on

• DataStructure/BinaryIndexedTree.cpp
• math/Inversion.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_5_D"
#include "./../math/Inversion.cpp"
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int& i : a) {
		cin >> i;
	}

	auto b = a;
	sort(b.begin(), b.end());
	for (int& i : a) {
		i = lower_bound(b.begin(), b.end(), i) - b.begin() + 1;
	}
	cout << Inversion(a, n) << '\n';
}

#line 1 "test/Inversion.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_5_D"
#line 2 "DataStructure/BinaryIndexedTree.cpp"
#include <vector>
#include <cassert>

template <class T> class BinaryIndexedTree {
public:
	using value_type = T;

private:
	int n, n2;
	std::vector<value_type> a;

public:
	BinaryIndexedTree(int n_) : n(n_), n2(1), a(n_ + 1) {
		while (n2 < n) n2 *= 2;
		n2 /= 2;
	}
	value_type operator()(int i) const {  // [0, i)
		if (i == 0) return 0;
		assert(0 < i && i <= n);
		value_type result = 0;
		for (; i > 0; i -= i & -i) {
			result += a[i];
		}
		return result;
	}
	value_type operator()(int l, int r) const {  // [l, r)
		return operator()(r) - operator()(l);
	}
	value_type operator[](int i) const {
		return operator()(i, i + 1);
	}
	void add(int i, value_type x) {
		assert(0 < ++i);
		for (; i <= n; i += i & -i) {
			a[i] += x;
		}
	}
	int lower_bound(value_type k) const {
		if (k <= 0) return 0;
		int result = 0;
		for (int i = n2; i > 0; i /= 2) {
			if (result + i <= n && a[result + i] < k) {
				k -= a[result + i];
				result += i;
			}
		}
		return result;
	}
	std::vector<value_type> to_a() const {
		std::vector<value_type> result(n);
		for (int i = 0; i < n; ++i) {
			result[i] = operator[](i);
		}
		return result;
	}
};
#line 4 "math/Inversion.cpp"

long long Inversion(const std::vector<int>& a, int max_val) {
	long long ans = 0;
	BinaryIndexedTree<int> bit(max_val + 1);
	for (std::size_t i = 0; i < a.size(); ++i) {
		ans += i - bit(a[i]);
		bit.add(a[i], 1);
	}
	return ans;
}
#line 3 "test/Inversion.test.cpp"
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int& i : a) {
		cin >> i;
	}

	auto b = a;
	sort(b.begin(), b.end());
	for (int& i : a) {
		i = lower_bound(b.begin(), b.end(), i) - b.begin() + 1;
	}
	cout << Inversion(a, n) << '\n';
}

Back to top page