cp-book

ecnerwala's competitive programming library

View the Project on GitHub ecnerwala/cp-book

:heavy_check_mark: verify/common_interval_decomposition_tree.test.cpp

View this file on GitHub · Last update: 2026-07-25 01:16:11-07:00

Problem: https://judge.yosupo.jp/problem/common_interval_decomposition_tree

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/common_interval_decomposition_tree

#include <bits/stdc++.h>
#include <cassert>

#include "perm_tree.hpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	int N; std::cin >> N;
	std::vector<int> P(N); for (auto& p : P) std::cin >> p;
	PermTree perm(P);
	int nxt_idx = 0;
	std::vector<std::tuple<int, std::array<int, 2>, bool>> res; res.reserve(2*N);
	[&](this auto&& self, int cur, int prv_idx, PermTree::NodeType par_type) -> void {
		if (perm[cur].type == PermTree::NodeType::PARTIAL || perm[cur].type == par_type) {
			self(perm[cur].c[0], prv_idx, par_type);
			self(perm[cur].c[1], prv_idx, par_type);
			return;
		}
		int cur_idx = nxt_idx++;
		res.push_back({prv_idx, {perm[cur].l, perm[cur].r}, perm[cur].type == PermTree::NodeType::FULL});
		if (perm[cur].type == PermTree::NodeType::LEAF) return;
		if (perm[cur].type == PermTree::NodeType::FULL) par_type = PermTree::NodeType::PARTIAL;
		else par_type = perm[cur].type;
		self(perm[cur].c[0], cur_idx, par_type);
		self(perm[cur].c[1], cur_idx, par_type);
	}(perm.root, -1, PermTree::NodeType::PARTIAL);
	std::cout << res.size() << '\n';
	for (auto [par, bounds, is_prime] : res) {
		std::cout << par << ' ' << bounds[0] << ' ' << bounds[1] << ' ' << (is_prime ? "prime" : "linear") << '\n';
	}

	return 0;
}

#include <bits/stdc++.h>
#line 1 "verify/common_interval_decomposition_tree.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/common_interval_decomposition_tree

#line 5 "verify/common_interval_decomposition_tree.test.cpp"

#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 7 "verify/common_interval_decomposition_tree.test.cpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	int N; std::cin >> N;
	std::vector<int> P(N); for (auto& p : P) std::cin >> p;
	PermTree perm(P);
	int nxt_idx = 0;
	std::vector<std::tuple<int, std::array<int, 2>, bool>> res; res.reserve(2*N);
	[&](this auto&& self, int cur, int prv_idx, PermTree::NodeType par_type) -> void {
		if (perm[cur].type == PermTree::NodeType::PARTIAL || perm[cur].type == par_type) {
			self(perm[cur].c[0], prv_idx, par_type);
			self(perm[cur].c[1], prv_idx, par_type);
			return;
		}
		int cur_idx = nxt_idx++;
		res.push_back({prv_idx, {perm[cur].l, perm[cur].r}, perm[cur].type == PermTree::NodeType::FULL});
		if (perm[cur].type == PermTree::NodeType::LEAF) return;
		if (perm[cur].type == PermTree::NodeType::FULL) par_type = PermTree::NodeType::PARTIAL;
		else par_type = perm[cur].type;
		self(perm[cur].c[0], cur_idx, par_type);
		self(perm[cur].c[1], cur_idx, par_type);
	}(perm.root, -1, PermTree::NodeType::PARTIAL);
	std::cout << res.size() << '\n';
	for (auto [par, bounds, is_prime] : res) {
		std::cout << par << ' ' << bounds[0] << ' ' << bounds[1] << ' ' << (is_prime ? "prime" : "linear") << '\n';
	}

	return 0;
}

// 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>
// 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;
}
};
// verify/common_interval_decomposition_tree.test.cpp
int main(){
std::ios_base::sync_with_stdio(false),std::cin.tie(nullptr);
int N;std::cin>>N;
std::vector<int>P(N);for(auto&p:P)std::cin>>p;
PermTree perm(P);
int nxt_idx=0;
std::vector<std::tuple<int,std::array<int,2>,bool>>res;res.reserve(2*N);
[&](this auto&&self,int cur,int prv_idx,PermTree::NodeType par_type)->void{
if(perm[cur].type==PermTree::NodeType::PARTIAL||perm[cur].type==par_type){
self(perm[cur].c[0],prv_idx,par_type);
self(perm[cur].c[1],prv_idx,par_type);
return;
}
int cur_idx=nxt_idx++;
res.push_back({prv_idx,{perm[cur].l,perm[cur].r},perm[cur].type==PermTree::NodeType::FULL});
if(perm[cur].type==PermTree::NodeType::LEAF)return;
if(perm[cur].type==PermTree::NodeType::FULL)par_type=PermTree::NodeType::PARTIAL;
else par_type=perm[cur].type;
self(perm[cur].c[0],cur_idx,par_type);
self(perm[cur].c[1],cur_idx,par_type);
}(perm.root,-1,PermTree::NodeType::PARTIAL);
std::cout<<res.size()<<'\n';
for(auto[par,bounds,is_prime]:res){
std::cout<<par<<' '<<bounds[0]<<' '<<bounds[1]<<' '<<(is_prime?"prime":"linear")<<'\n';
}
return 0;
}
#pragma GCC diagnostic pop
// clang-format on
// @formatter:on

Test cases

Env Name Status Elapsed Memory
g++-sanitizer almost_straight_00 :heavy_check_mark: AC 1906 ms 241 MB
g++-sanitizer almost_straight_01 :heavy_check_mark: AC 2107 ms 79 MB
g++-sanitizer almost_straight_02 :heavy_check_mark: AC 257 ms 32 MB
g++-sanitizer ascending_order_00 :heavy_check_mark: AC 1885 ms 241 MB
g++-sanitizer ascending_order_01 :heavy_check_mark: AC 2252 ms 284 MB
g++-sanitizer ascending_order_02 :heavy_check_mark: AC 279 ms 43 MB
g++-sanitizer descending_order_00 :heavy_check_mark: AC 1881 ms 241 MB
g++-sanitizer descending_order_01 :heavy_check_mark: AC 2227 ms 284 MB
g++-sanitizer descending_order_02 :heavy_check_mark: AC 283 ms 43 MB
g++-sanitizer example_00 :heavy_check_mark: AC 16 ms 9 MB
g++-sanitizer example_01 :heavy_check_mark: AC 14 ms 9 MB
g++-sanitizer example_02 :heavy_check_mark: AC 20 ms 9 MB
g++-sanitizer killer_case_00 :heavy_check_mark: AC 395 ms 65 MB
g++-sanitizer killer_case_01 :heavy_check_mark: AC 745 ms 66 MB
g++-sanitizer killer_case_02 :heavy_check_mark: AC 386 ms 65 MB
g++-sanitizer killer_case_03 :heavy_check_mark: AC 383 ms 65 MB
g++-sanitizer killer_case_04 :heavy_check_mark: AC 384 ms 64 MB
g++-sanitizer killer_straight_00 :heavy_check_mark: AC 429 ms 66 MB
g++-sanitizer max_random_00 :heavy_check_mark: AC 2411 ms 306 MB
g++-sanitizer max_random_01 :heavy_check_mark: AC 2426 ms 306 MB
g++-sanitizer max_random_02 :heavy_check_mark: AC 2467 ms 306 MB
g++-sanitizer random_00 :heavy_check_mark: AC 1896 ms 241 MB
g++-sanitizer random_01 :heavy_check_mark: AC 2280 ms 284 MB
g++-sanitizer random_02 :heavy_check_mark: AC 280 ms 43 MB
g++-sanitizer small_random_00 :heavy_check_mark: AC 14 ms 9 MB
g++-sanitizer small_random_01 :heavy_check_mark: AC 12 ms 9 MB
g++-sanitizer small_random_02 :heavy_check_mark: AC 18 ms 9 MB
g++-sanitizer swap_random_00 :heavy_check_mark: AC 1920 ms 228 MB
g++-sanitizer swap_random_01 :heavy_check_mark: AC 2214 ms 223 MB
g++-sanitizer swap_random_02 :heavy_check_mark: AC 269 ms 39 MB
g++ almost_straight_00 :heavy_check_mark: AC 142 ms 75 MB
g++ almost_straight_01 :heavy_check_mark: AC 149 ms 43 MB
g++ almost_straight_02 :heavy_check_mark: AC 19 ms 11 MB
g++ ascending_order_00 :heavy_check_mark: AC 144 ms 75 MB
g++ ascending_order_01 :heavy_check_mark: AC 183 ms 89 MB
g++ ascending_order_02 :heavy_check_mark: AC 22 ms 13 MB
g++ descending_order_00 :heavy_check_mark: AC 148 ms 75 MB
g++ descending_order_01 :heavy_check_mark: AC 168 ms 89 MB
g++ descending_order_02 :heavy_check_mark: AC 21 ms 13 MB
g++ example_00 :heavy_check_mark: AC 3 ms 4 MB
g++ example_01 :heavy_check_mark: AC 2 ms 4 MB
g++ example_02 :heavy_check_mark: AC 2 ms 4 MB
g++ killer_case_00 :heavy_check_mark: AC 197 ms 45 MB
g++ killer_case_01 :heavy_check_mark: AC 227 ms 45 MB
g++ killer_case_02 :heavy_check_mark: AC 211 ms 45 MB
g++ killer_case_03 :heavy_check_mark: AC 195 ms 45 MB
g++ killer_case_04 :heavy_check_mark: AC 188 ms 45 MB
g++ killer_straight_00 :heavy_check_mark: AC 213 ms 46 MB
g++ max_random_00 :heavy_check_mark: AC 184 ms 95 MB
g++ max_random_01 :heavy_check_mark: AC 183 ms 95 MB
g++ max_random_02 :heavy_check_mark: AC 182 ms 95 MB
g++ random_00 :heavy_check_mark: AC 142 ms 75 MB
g++ random_01 :heavy_check_mark: AC 179 ms 89 MB
g++ random_02 :heavy_check_mark: AC 21 ms 13 MB
g++ small_random_00 :heavy_check_mark: AC 3 ms 4 MB
g++ small_random_01 :heavy_check_mark: AC 2 ms 4 MB
g++ small_random_02 :heavy_check_mark: AC 2 ms 4 MB
g++ swap_random_00 :heavy_check_mark: AC 140 ms 72 MB
g++ swap_random_01 :heavy_check_mark: AC 176 ms 75 MB
g++ swap_random_02 :heavy_check_mark: AC 21 ms 13 MB
Back to top page