Permutation Tree

tree/permutation_tree.hpp · GitHub で見る

共通ページ

#include "lib/tree/permutation_tree.hpp"
#include <iostream>

PermutationTree tree(std::vector<int>{1, 0, 3, 2});
std::cout << tree.count_intervals() << '\n'; // 7
for (int v : tree.children(tree.root())) {
	std::cout << tree[v].l << ' ' << tree[v].r << '\n';
}
// 0 2
// 2 4

順列の共通区間分解木を作ります。入力は 0..n-1 を一度ずつ含む順列です。std::vector<int>・std::array<int,n> などの std::span<const int> に変換できる列を渡せます。入力を書き換えず、元の入力配列は構築後に破棄できます。長さは INT_MAX/2 以下としてください。

区間 [l,r) に現れる値が連続する、つまり max - min = r - l - 1 となる区間を共通区間と呼びます。木の頂点は、他の共通区間と部分的に重ならない共通区間（strong interval）に対応します。葉は各要素、根は順列全体です。

操作	内容・返り値	計算量
PermutationTree()	空の木を作る	\(O(1)\)
PermutationTree(p)	順列 p から構築	\(O(n+b\log b)\)
build(p)	順列から再構築。空列にも対応	\(O(n+b\log b)\)
size()	葉と内部頂点を合わせた頂点数	\(O(1)\)
length()	入力順列の長さ	\(O(1)\)
empty()	入力順列が空か	\(O(1)\)
root()	根の頂点 ID。空なら -1	\(O(1)\)
leaf(i)	入力位置 i に対応する葉の ID。i と等しい	\(O(1)\)
operator[](v)	頂点 v の Node への const 参照	\(O(1)\)
nodes()	全頂点の vector<Node> への const 参照	\(O(1)\)
children(v)	子の ID を位置区間の左端順に並べた span<const int>	\(O(1)\)
order()	根からの幅優先順の頂点 ID を返す span<const int>	\(O(1)\)
count_intervals()	長さ 1 を含む全共通区間の個数を int64_t で返す。空なら 0	\(O(1)\)

Node の要素	内容
parent	親の ID。根は -1
l / r	入力位置の半開区間 [l,r)
lo / hi	値の半開区間 [lo,hi)。常に r-l = hi-lo
type	PermutationTree::Type による頂点の種類

Type の値	内容
Type::Leaf	長さ 1 の葉
Type::Increasing	子の値区間が左から増加する linear 頂点
Type::Decreasing	子の値区間が左から減少する linear 頂点
Type::Prime	それ以外の内部頂点

Increasing・Decreasing の頂点では、連続する任意の子の位置区間を合わせても共通区間になります。全共通区間は、木の頂点の区間と、このような子の連続区間の和集合で表せます。

頂点 ID は構築順なので、親子の ID の大小関係は保証しません。葉の ID は 0..n-1 です。order() では必ず親が子より先に現れるため、その逆順で木 DP を行えます。子は必ず左から右の順です。空でなければ頂点数は最大 2n-1 です。木が深い場合も、構築と走査順の生成に再帰を使いません。

コピー・ムーブに対応します。返された参照や span は再構築・代入・移動・破棄で無効になる場合があります。再構築では出力配列の容量を再利用します。

長さを \(n\)、内部 RMQ のブロック数を \(b=\lceil n/32\rceil\) とすると、構築時間・一時空間は \(O(n+b\log b)\) です。構築後の保持空間は \(O(n)\)、表の参照操作は全て \(O(1)\) です。空列の構築は \(O(1)\) です。

依存ライブラリ

• Default Init Allocator
• Static Range Min
• Sparse Table

検証コード

• test/permutation_tree.test.cpp

コード

#ifndef PERMUTATION_TREE_HPP
#define PERMUTATION_TREE_HPP

#include "../components/static_range_min.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <span>
#include <vector>

class PermutationTree {
  public:
	enum class Type : unsigned char { Leaf, Increasing, Decreasing, Prime };
	struct Node {
		int parent, l, r, lo, hi;
		Type type;
	};

  private:
	int root_ = -1;
	std::int64_t count_ = 0;
	std::vector<Node> nodes_;
	std::vector<int> offsets_, children_, order_;
	int add_node(int l, int r, int lo, int hi, Type type) {
		int id = size();
		nodes_.push_back({-1, l, r, lo, hi, type});
		return id;
	}
	void pack(int n) {
		int m = size();
		offsets_.assign(m + 1, 0);
		for (auto &node : nodes_) if (node.parent >= 0) ++offsets_[node.parent + 1];
		for (int i = 0; i < m; ++i) offsets_[i + 1] += offsets_[i];
		children_.resize(m - 1);
		std::vector<int> cursor = offsets_;
		for (int i = 0; i < n; ++i) {
			int v = i;
			while (nodes_[v].parent >= 0) {
				int parent = nodes_[v].parent;
				children_[cursor[parent]++] = v;
				if (nodes_[parent].l != i) break;
				v = parent;
			}
		}
		count_ = n;
		for (int i = n; i < m; ++i) {
			std::int64_t k = offsets_[i + 1] - offsets_[i];
			count_ += nodes_[i].type == Type::Prime ? 1 : k * (k - 1) / 2;
		}
		order_.clear();
		order_.reserve(m);
		order_.push_back(root_);
		for (int i = 0; i < m; ++i)
			for (int child : children(order_[i])) order_.push_back(child);
	}

  public:
	PermutationTree() = default;
	explicit PermutationTree(std::span<const int> permutation) { build(permutation); }
	void build(std::span<const int> permutation) {
		assert(permutation.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
		int n = static_cast<int>(permutation.size());
		root_ = -1;
		count_ = 0;
		nodes_.clear();
		offsets_.clear();
		children_.clear();
		order_.clear();
		if (!n) return;
		nodes_.reserve(2 * std::size_t(n) - 1);
		std::vector<int> inverse(n, -1);
		for (int i = 0; i < n; ++i) {
			int x = permutation[i];
			assert(0 <= x && x < n && inverse[x] < 0);
			inverse[x] = i;
			add_node(i, i + 1, x, x + 1, Type::Leaf);
		}
		struct Frame { int l, lo, hi; };
		struct Interval { int l, r, lo, hi; };
		std::vector<Interval> intervals;
		{
			StaticRangeMin minimum(std::move(inverse));
			std::vector<Frame> stack;
			stack.reserve(n);
			intervals.reserve(n - 1);
			for (int r = 1; r <= n; ++r) {
				int x = permutation[r - 1];
				Frame current{r - 1, x, x + 1};
				while (!stack.empty()) {
					auto &top = stack.back();
					top.lo = std::min(top.lo, current.lo);
					top.hi = std::max(top.hi, current.hi);
					if (top.hi - top.lo == r - top.l) {
						current = top;
						intervals.push_back({top.l, r, top.lo, top.hi});
						stack.pop_back();
					} else if (minimum.prod(top.lo, top.hi) < top.l) {
						Frame removed = top;
						stack.pop_back();
						assert(!stack.empty());
						stack.back().lo = std::min(stack.back().lo, removed.lo);
						stack.back().hi = std::max(stack.back().hi, removed.hi);
					} else break;
				}
				stack.push_back(current);
			}
			assert(stack.size() == 1 && stack[0].l == 0);
		}
		std::vector<int> at(n), next(n);
		for (int i = 0; i < n; ++i) at[i] = i, next[i] = i + 1;
		for (auto interval : intervals) {
			int l = interval.l, r = interval.r, middle = next[l];
			int first = at[l], id;
			if (next[middle] == r) {
				int second = at[middle];
				Type type = nodes_[first].hi == nodes_[second].lo ? Type::Increasing : Type::Decreasing;
				if (nodes_[first].type == type) {
					id = first;
					nodes_[id].r = r;
					nodes_[id].lo = interval.lo;
					nodes_[id].hi = interval.hi;
					nodes_[second].parent = id;
				} else {
					id = add_node(l, r, interval.lo, interval.hi, type);
					nodes_[first].parent = nodes_[second].parent = id;
				}
			} else {
				id = add_node(l, r, interval.lo, interval.hi, Type::Prime);
				for (int i = l; i < r; i = next[i]) nodes_[at[i]].parent = id;
			}
			at[l] = id;
			next[l] = r;
		}
		root_ = at[0];
		assert(next[0] == n);
		pack(n);
	}
	int size() const { return static_cast<int>(nodes_.size()); }
	bool empty() const { return nodes_.empty(); }
	int root() const { return empty() ? -1 : root_; }
	int length() const { return empty() ? 0 : nodes_[root_].r; }
	int leaf(int i) const { assert(0 <= i && i < length()); return i; }
	const Node &operator[](int i) const {
		assert(0 <= i && i < size());
		return nodes_[i];
	}
	const std::vector<Node> &nodes() const { return nodes_; }
	std::span<const int> children(int v) const {
		assert(0 <= v && v < size());
		return std::span<const int>(children_).subspan(offsets_[v], offsets_[v + 1] - offsets_[v]);
	}
	std::span<const int> order() const { return order_; }
	std::int64_t count_intervals() const { return empty() ? 0 : count_; }
};

#endif

Back to top page