compression (座標圧縮)
(src/algorithm/compression.hpp)

• View this file on GitHub
• Last update: 2023-01-16 00:44:12+09:00
• Include: #include "src/algorithm/compression.hpp"

概要

長さ $N$ の列 $A$ について以下の情報を管理します

• 要素 $v$ が $A$ の中で何番目に小さいか。

機能

zawa::compression<T>(const std::vector<T>& as)

• コンストラクタ
• as 入力
• 計算量 : $O(N\log N)$

int zawa::compression<T>::operator[](const T& val)

• valが $A$ の要素で何番目に小さいかを返す。0-indexed
• 計算量 : $O(\log N)$

int zawa::compression<T>::get(std::size_t i)

• $A_i$ が $A$ の要素で何番目に小さいかを返す。0-indexed
• 計算量 : $O(\log N)$

std::size_t zawa::compression<T>::size()

• $A$ に含まれる要素の種類数を返す
• 計算量 : $O(1)$

Verified with

• test/ABC285-D.test.cpp
• test/ARC075-E.test.cpp
• test/compression.test.cpp

Code

#pragma once

#include <vector>
#include <algorithm>

namespace zawa {

template <class T>
class compression {
private:
	std::vector<T> as;
	std::vector<T> uniqued;

public:
	compression(const std::vector<T>& as) : as(as), uniqued(as) {
		std::sort(uniqued.begin(), uniqued.end());
		uniqued.erase(std::unique(uniqued.begin(), uniqued.end()), uniqued.end());
	}

	int operator[](const T& val) {
		return std::lower_bound(uniqued.begin(), uniqued.end(), val) - uniqued.begin();
	}

	int get(std::size_t i) {
		return (*this)[as[i]];
	}

	std::size_t size() {
		return uniqued.size();
	}
};

} // namespace zawa

#line 2 "src/algorithm/compression.hpp"

#include <vector>
#include <algorithm>

namespace zawa {

template <class T>
class compression {
private:
	std::vector<T> as;
	std::vector<T> uniqued;

public:
	compression(const std::vector<T>& as) : as(as), uniqued(as) {
		std::sort(uniqued.begin(), uniqued.end());
		uniqued.erase(std::unique(uniqued.begin(), uniqued.end()), uniqued.end());
	}

	int operator[](const T& val) {
		return std::lower_bound(uniqued.begin(), uniqued.end(), val) - uniqued.begin();
	}

	int get(std::size_t i) {
		return (*this)[as[i]];
	}

	std::size_t size() {
		return uniqued.size();
	}
};

} // namespace zawa

Back to top page