cp-book

ecnerwala's competitive programming library

View the Project on GitHub ecnerwala/cp-book

🧪 perm_tree.test.cpp

View this file on GitHub · Last update: 2026-01-30 00:07:06-08:00

Depends on

Code

#include "perm_tree.hpp"

#include <catch2/catch_test_macros.hpp>
#include <bits/stdc++.h>

void check_tree(std::vector<int> A) {
	int N = int(A.size());
	std::vector<std::pair<std::array<int, 2>, std::array<int, 2>>> actual_ranges;
	for (int i = 0; i < N; i++) {
		int lo = A[i], hi = A[i];
		for (int j = i; j < N; j++) {
			lo = std::min(lo, A[j]);
			hi = std::max(hi, A[j]);
			assert(hi - lo >= j - i);
			if (hi - lo == j - i) {
				actual_ranges.push_back({{i, j}, {lo, hi}});
			}
		}
	}

	PermTree tree(A);
	std::vector<std::pair<std::array<int, 2>, std::array<int, 2>>> computed_ranges;
	for (int n = 0; n < tree.size(); n++) {
		const auto& node = tree[n];
		if (node.type != PermTree::NodeType::PARTIAL) {
			computed_ranges.push_back({{node.l, node.r}, {node.lo, node.hi}});
		}
		if (node.type == PermTree::NodeType::LEAF) {
			REQUIRE(node.c[0] == -1);
			REQUIRE(node.c[1] == -1);
			REQUIRE(node.l == n/2);
			REQUIRE(node.r == n/2);
			REQUIRE(node.lo == A[n/2]);
			REQUIRE(node.hi == A[n/2]);
			continue;
		}
		REQUIRE(node.c[0] != -1);
		REQUIRE(node.c[1] != -1);
		REQUIRE(node.l == tree[node.c[0]].l);
		REQUIRE(node.r == tree[node.c[1]].r);
		REQUIRE(tree[node.c[0]].r + 1 == tree[node.c[1]].l);
		REQUIRE(node.lo == std::min(tree[node.c[0]].lo, tree[node.c[1]].lo));
		REQUIRE(node.hi == std::max(tree[node.c[0]].hi, tree[node.c[1]].hi));
		if (node.type == PermTree::NodeType::FULL) {
			// There should be at least 3 pieces
			REQUIRE((
				tree[node.c[0]].type == PermTree::NodeType::PARTIAL
				|| tree[node.c[1]].type == PermTree::NodeType::PARTIAL
			));
		}
		if (node.type == PermTree::NodeType::INCR) {
			REQUIRE(tree[node.c[0]].hi + 1 == tree[node.c[1]].lo);

			REQUIRE(tree[node.c[1]].type != PermTree::NodeType::INCR);
			for (int cur = node.c[0]; tree[cur].type == PermTree::NodeType::INCR; cur = tree[cur].c[0]) {
				int ch = tree[cur].c[1];
				computed_ranges.push_back({{tree[ch].l, node.r}, {tree[ch].lo, node.hi}});
			}
		}
		if (node.type == PermTree::NodeType::DECR) {
			REQUIRE(tree[node.c[0]].lo - 1 == tree[node.c[1]].hi);

			REQUIRE(tree[node.c[1]].type != PermTree::NodeType::DECR);
			for (int cur = node.c[0]; tree[cur].type == PermTree::NodeType::DECR; cur = tree[cur].c[0]) {
				int ch = tree[cur].c[1];
				computed_ranges.push_back({{tree[ch].l, node.r}, {node.lo, tree[ch].hi}});
			}
		}
	}
	std::sort(computed_ranges.begin(), computed_ranges.end());
	REQUIRE(actual_ranges == computed_ranges);
}

TEST_CASE("Permutation Tree", "[perm_tree]") {
	for (int N = 1; N <= 7; N++) {
		std::vector<int> A(N);
		std::iota(A.begin(), A.end(), 0);
		do {
			check_tree(A);
		} while (next_permutation(A.begin(), A.end()));
	}
}

#include <vector>
#include <array>
#include <cassert>
#include <catch2/catch_test_macros.hpp>
#include <bits/stdc++.h>
#line 2 "src/perm_tree.hpp"

#line 6 "src/perm_tree.hpp"

class PermTree {
	// The tree is "left-associative": INCR/DECR nodes are structured as (1 INCR 2) INCR 3...
public:
	enum class NodeType {
		LEAF,
		INCR,
		DECR,
		FULL,
		PARTIAL,
	};

	struct Node {
		std::array<int, 2> c;
		NodeType type;
		int l, r, lo, hi;
	};

	std::vector<Node> nodes;
	int root = -1;

	PermTree() {}
	Node& operator [] (int idx) { return nodes[idx]; }
	const Node& operator [] (int idx) const { return nodes[idx]; }

	int size() const { return int(nodes.size()); }

	PermTree(const std::vector<int>& A) : nodes(A.empty() ? 0 : int(A.size())*2-1) {
		if (A.empty()) { root = -1; return; }
		int N = int(A.size());
		std::vector<int> nxt_earlier(N);
		std::vector<int> prv_earlier(N);
		for (int i = 0; i < N; i++) {
			nxt_earlier[i] = i+1;
			prv_earlier[i] = i-1;
		}
		for (int i = N-1; i >= 0; i--) {
			int a = A[i];
			int p = prv_earlier[a];
			int n = nxt_earlier[a];
			if (p != -1) nxt_earlier[p] = n;
			if (n != N) prv_earlier[n] = p;
		}

		struct cnd_t {
			int left;
			int lo;
			int lo_gap;
			int hi;
			int hi_gap;
			int node;
		};

		std::vector<cnd_t> stk; stk.reserve(N);

		for (int i = 0; i < N; i++) {
			int a = A[i];
			while (true) {
				if (!stk.empty() && (a < stk.back().lo_gap || a > stk.back().hi_gap)) {
					assert(stk.size() >= 2);
					stk.end()[-2].lo = std::min(stk.end()[-2].lo, stk.back().lo);
					stk.end()[-2].hi = std::max(stk.end()[-2].hi, stk.back().hi);

					int n = 2 * stk.back().left - 1;
					nodes[n].c = {stk.end()[-2].node, stk.end()[-1].node};
					nodes[n].type = NodeType::PARTIAL;
					nodes[n].l = stk.end()[-2].left;
					nodes[n].r = i-1;
					nodes[n].lo = stk.end()[-2].lo;
					nodes[n].hi = stk.end()[-2].hi;

					stk.pop_back();

					stk.back().node = n;
				} else {
					break;
				}
			}

			stk.push_back({i, a, prv_earlier[a]+1, a, nxt_earlier[a]-1, 2*i});
			nodes[2*i].type = NodeType::LEAF;
			nodes[2*i].c = {-1, -1};
			nodes[2*i].l = nodes[2*i].r = i;
			nodes[2*i].lo = nodes[2*i].hi = a;

			while (stk.size() >= 2 && std::max(stk.back().hi, stk.end()[-2].hi) - std::min(stk.back().lo, stk.end()[-2].lo) == i - stk.end()[-2].left) {
				// merge these two nodes into one
				stk.end()[-2].lo = std::min(stk.end()[-2].lo, stk.back().lo);
				stk.end()[-2].hi = std::max(stk.end()[-2].hi, stk.back().hi);

				int n = 2 * stk.back().left - 1;
				nodes[n].c = {stk.end()[-2].node, stk.end()[-1].node};
				if (stk.end()[-2].lo == stk.end()[-1].lo) {
					nodes[n].type = NodeType::DECR;
				} else if (stk.end()[-2].hi == stk.end()[-1].hi) {
					nodes[n].type = NodeType::INCR;
				} else {
					nodes[n].type = NodeType::FULL;
				}
				nodes[n].l = stk.end()[-2].left;
				nodes[n].r = i;
				nodes[n].lo = stk.end()[-2].lo;
				nodes[n].hi = stk.end()[-2].hi;

				stk.pop_back();
				stk.back().node = n;
			}
		}

		assert(stk.size() == 1);
		root = stk.back().node;
	}
};
#line 2 "src/perm_tree.test.cpp"

#line 5 "src/perm_tree.test.cpp"

void check_tree(std::vector<int> A) {
	int N = int(A.size());
	std::vector<std::pair<std::array<int, 2>, std::array<int, 2>>> actual_ranges;
	for (int i = 0; i < N; i++) {
		int lo = A[i], hi = A[i];
		for (int j = i; j < N; j++) {
			lo = std::min(lo, A[j]);
			hi = std::max(hi, A[j]);
			assert(hi - lo >= j - i);
			if (hi - lo == j - i) {
				actual_ranges.push_back({{i, j}, {lo, hi}});
			}
		}
	}

	PermTree tree(A);
	std::vector<std::pair<std::array<int, 2>, std::array<int, 2>>> computed_ranges;
	for (int n = 0; n < tree.size(); n++) {
		const auto& node = tree[n];
		if (node.type != PermTree::NodeType::PARTIAL) {
			computed_ranges.push_back({{node.l, node.r}, {node.lo, node.hi}});
		}
		if (node.type == PermTree::NodeType::LEAF) {
			REQUIRE(node.c[0] == -1);
			REQUIRE(node.c[1] == -1);
			REQUIRE(node.l == n/2);
			REQUIRE(node.r == n/2);
			REQUIRE(node.lo == A[n/2]);
			REQUIRE(node.hi == A[n/2]);
			continue;
		}
		REQUIRE(node.c[0] != -1);
		REQUIRE(node.c[1] != -1);
		REQUIRE(node.l == tree[node.c[0]].l);
		REQUIRE(node.r == tree[node.c[1]].r);
		REQUIRE(tree[node.c[0]].r + 1 == tree[node.c[1]].l);
		REQUIRE(node.lo == std::min(tree[node.c[0]].lo, tree[node.c[1]].lo));
		REQUIRE(node.hi == std::max(tree[node.c[0]].hi, tree[node.c[1]].hi));
		if (node.type == PermTree::NodeType::FULL) {
			// There should be at least 3 pieces
			REQUIRE((
				tree[node.c[0]].type == PermTree::NodeType::PARTIAL
				|| tree[node.c[1]].type == PermTree::NodeType::PARTIAL
			));
		}
		if (node.type == PermTree::NodeType::INCR) {
			REQUIRE(tree[node.c[0]].hi + 1 == tree[node.c[1]].lo);

			REQUIRE(tree[node.c[1]].type != PermTree::NodeType::INCR);
			for (int cur = node.c[0]; tree[cur].type == PermTree::NodeType::INCR; cur = tree[cur].c[0]) {
				int ch = tree[cur].c[1];
				computed_ranges.push_back({{tree[ch].l, node.r}, {tree[ch].lo, node.hi}});
			}
		}
		if (node.type == PermTree::NodeType::DECR) {
			REQUIRE(tree[node.c[0]].lo - 1 == tree[node.c[1]].hi);

			REQUIRE(tree[node.c[1]].type != PermTree::NodeType::DECR);
			for (int cur = node.c[0]; tree[cur].type == PermTree::NodeType::DECR; cur = tree[cur].c[0]) {
				int ch = tree[cur].c[1];
				computed_ranges.push_back({{tree[ch].l, node.r}, {node.lo, tree[ch].hi}});
			}
		}
	}
	std::sort(computed_ranges.begin(), computed_ranges.end());
	REQUIRE(actual_ranges == computed_ranges);
}

TEST_CASE("Permutation Tree", "[perm_tree]") {
	for (int N = 1; N <= 7; N++) {
		std::vector<int> A(N);
		std::iota(A.begin(), A.end(), 0);
		do {
			check_tree(A);
		} while (next_permutation(A.begin(), A.end()));
	}
}

// clang-format off
// @formatter:off
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#pragma GCC diagnostic ignored "-Wmultistatement-macros"
#include <bits/stdc++.h>
#include <cassert>
#include <catch2/catch_test_macros.hpp>
// src/perm_tree.hpp
class PermTree{
public:
enum class NodeType{
LEAF,
INCR,
DECR,
FULL,
PARTIAL,
};
struct Node{
std::array<int,2>c;
NodeType type;
int l,r,lo,hi;
};
std::vector<Node>nodes;
int root=-1;
PermTree(){}
Node&operator[](int idx){return nodes[idx];}
const Node&operator[](int idx)const{return nodes[idx];}
int size()const{return int(nodes.size());}
PermTree(const std::vector<int>&A):nodes(A.empty()?0:int(A.size())*2-1){
if(A.empty()){root=-1;return;}
int N=int(A.size());
std::vector<int>nxt_earlier(N);
std::vector<int>prv_earlier(N);
for(int i=0;i<N;i++){
nxt_earlier[i]=i+1;
prv_earlier[i]=i-1;
}
for(int i=N-1;i>=0;i--){
int a=A[i];
int p=prv_earlier[a];
int n=nxt_earlier[a];
if(p!=-1)nxt_earlier[p]=n;
if(n!=N)prv_earlier[n]=p;
}
struct cnd_t{
int left;
int lo;
int lo_gap;
int hi;
int hi_gap;
int node;
};
std::vector<cnd_t>stk;stk.reserve(N);
for(int i=0;i<N;i++){
int a=A[i];
while(true){
if(!stk.empty()&&(a<stk.back().lo_gap||a>stk.back().hi_gap)){
assert(stk.size()>=2);
stk.end()[-2].lo=std::min(stk.end()[-2].lo,stk.back().lo);
stk.end()[-2].hi=std::max(stk.end()[-2].hi,stk.back().hi);
int n=2*stk.back().left-1;
nodes[n].c={stk.end()[-2].node,stk.end()[-1].node};
nodes[n].type=NodeType::PARTIAL;
nodes[n].l=stk.end()[-2].left;
nodes[n].r=i-1;
nodes[n].lo=stk.end()[-2].lo;
nodes[n].hi=stk.end()[-2].hi;
stk.pop_back();
stk.back().node=n;
}else{
break;
}
}
stk.push_back({i,a,prv_earlier[a]+1,a,nxt_earlier[a]-1,2*i});
nodes[2*i].type=NodeType::LEAF;
nodes[2*i].c={-1,-1};
nodes[2*i].l=nodes[2*i].r=i;
nodes[2*i].lo=nodes[2*i].hi=a;
while(stk.size()>=2&&std::max(stk.back().hi,stk.end()[-2].hi)-std::min(stk.back().lo,stk.end()[-2].lo)==i-stk.end()[-2].left){
stk.end()[-2].lo=std::min(stk.end()[-2].lo,stk.back().lo);
stk.end()[-2].hi=std::max(stk.end()[-2].hi,stk.back().hi);
int n=2*stk.back().left-1;
nodes[n].c={stk.end()[-2].node,stk.end()[-1].node};
if(stk.end()[-2].lo==stk.end()[-1].lo){
nodes[n].type=NodeType::DECR;
}else if(stk.end()[-2].hi==stk.end()[-1].hi){
nodes[n].type=NodeType::INCR;
}else{
nodes[n].type=NodeType::FULL;
}
nodes[n].l=stk.end()[-2].left;
nodes[n].r=i;
nodes[n].lo=stk.end()[-2].lo;
nodes[n].hi=stk.end()[-2].hi;
stk.pop_back();
stk.back().node=n;
}
}
assert(stk.size()==1);
root=stk.back().node;
}
};
// src/perm_tree.test.cpp
void check_tree(std::vector<int>A){
int N=int(A.size());
std::vector<std::pair<std::array<int,2>,std::array<int,2>>>actual_ranges;
for(int i=0;i<N;i++){
int lo=A[i],hi=A[i];
for(int j=i;j<N;j++){
lo=std::min(lo,A[j]);
hi=std::max(hi,A[j]);
assert(hi-lo>=j-i);
if(hi-lo==j-i){
actual_ranges.push_back({{i,j},{lo,hi}});
}
}
}
PermTree tree(A);
std::vector<std::pair<std::array<int,2>,std::array<int,2>>>computed_ranges;
for(int n=0;n<tree.size();n++){
const auto&node=tree[n];
if(node.type!=PermTree::NodeType::PARTIAL){
computed_ranges.push_back({{node.l,node.r},{node.lo,node.hi}});
}
if(node.type==PermTree::NodeType::LEAF){
REQUIRE(node.c[0]==-1);
REQUIRE(node.c[1]==-1);
REQUIRE(node.l==n/2);
REQUIRE(node.r==n/2);
REQUIRE(node.lo==A[n/2]);
REQUIRE(node.hi==A[n/2]);
continue;
}
REQUIRE(node.c[0]!=-1);
REQUIRE(node.c[1]!=-1);
REQUIRE(node.l==tree[node.c[0]].l);
REQUIRE(node.r==tree[node.c[1]].r);
REQUIRE(tree[node.c[0]].r+1==tree[node.c[1]].l);
REQUIRE(node.lo==std::min(tree[node.c[0]].lo,tree[node.c[1]].lo));
REQUIRE(node.hi==std::max(tree[node.c[0]].hi,tree[node.c[1]].hi));
if(node.type==PermTree::NodeType::FULL){
REQUIRE((
tree[node.c[0]].type==PermTree::NodeType::PARTIAL
||tree[node.c[1]].type==PermTree::NodeType::PARTIAL
));
}
if(node.type==PermTree::NodeType::INCR){
REQUIRE(tree[node.c[0]].hi+1==tree[node.c[1]].lo);
REQUIRE(tree[node.c[1]].type!=PermTree::NodeType::INCR);
for(int cur=node.c[0];tree[cur].type==PermTree::NodeType::INCR;cur=tree[cur].c[0]){
int ch=tree[cur].c[1];
computed_ranges.push_back({{tree[ch].l,node.r},{tree[ch].lo,node.hi}});
}
}
if(node.type==PermTree::NodeType::DECR){
REQUIRE(tree[node.c[0]].lo-1==tree[node.c[1]].hi);
REQUIRE(tree[node.c[1]].type!=PermTree::NodeType::DECR);
for(int cur=node.c[0];tree[cur].type==PermTree::NodeType::DECR;cur=tree[cur].c[0]){
int ch=tree[cur].c[1];
computed_ranges.push_back({{tree[ch].l,node.r},{node.lo,tree[ch].hi}});
}
}
}
std::sort(computed_ranges.begin(),computed_ranges.end());
REQUIRE(actual_ranges==computed_ranges);
}
TEST_CASE("Permutation Tree","[perm_tree]"){
for(int N=1;N<=7;N++){
std::vector<int>A(N);
std::iota(A.begin(),A.end(),0);
do{
check_tree(A);
}while(next_permutation(A.begin(),A.end()));
}
}
#pragma GCC diagnostic pop
// clang-format on
// @formatter:on
Back to top page