座標圧縮 (src/vector/coordinate_compression.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2023-09-06 14:54:16+09:00
Include: #include "src/vector/coordinate_compression.hpp"

Required by

転倒数 (src/vector/inversion_number.hpp)

Verified with

test/vector/inversion_number/aoj_alds1_5_d.test.cpp

Code

#ifndef VECTOR_COORDINATE_COMPRESSION
#define VECTOR_COORDINATE_COMPRESSION

#include <algorithm>
#include <vector>

template<class T>
class CoordinateCompression {
private:
	std::vector<T> x;

public:
	CoordinateCompression(std::vector<T> const &v) : x(v.size()) {
		std::partial_sort_copy(v.begin(), v.end(), x.begin(), x.end());
		x.erase(std::unique(x.begin(), x.end()), x.end());
	}

	[[nodiscard]] int size() const { return x.size(); }

	T operator[](int k) { return x[k]; }

	[[nodiscard]] int get(T const &v) const {
		return std::lower_bound(x.begin(), x.end(), v) - x.begin();
	}
};

#endif // VECTOR_COORDINATE_COMPRESSION

#line 1 "src/vector/coordinate_compression.hpp"



#include <algorithm>
#include <vector>

template<class T>
class CoordinateCompression {
private:
	std::vector<T> x;

public:
	CoordinateCompression(std::vector<T> const &v) : x(v.size()) {
		std::partial_sort_copy(v.begin(), v.end(), x.begin(), x.end());
		x.erase(std::unique(x.begin(), x.end()), x.end());
	}

	[[nodiscard]] int size() const { return x.size(); }

	T operator[](int k) { return x[k]; }

	[[nodiscard]] int get(T const &v) const {
		return std::lower_bound(x.begin(), x.end(), v) - x.begin();
	}
};