#1081607 (C++23) No.3134 二分探索木

• 問題: No.3134 二分探索木
• ユーザー: Aeren
• 提出日時: 2025-05-02 21:34:12
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 186 ms / 2,000 ms
• コード長: 9,609 bytes
• コンパイル時間: 4,220 ms
• コンパイル使用メモリ: 309,972 KB
• 実行使用メモリ: 62,052 KB
• 最終ジャッジ日時: 2025-05-02 21:34:19
• 合計ジャッジ時間: 6,939 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
sample	AC * 5
other	AC * 15

ソースコード

// #include <bits/allocator.h> // Temp fix for gcc13 global pragma
// #pragma GCC target("avx2,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
#ifdef LOCAL
	#include "Debug.h"
#else
	#define debug_endl() 42
	#define debug(...) 42
	#define debug2(...) 42
	#define debug_bin(...) 42
#endif

template<class T>
struct graph{
	using Weight_t = T;
	struct Edge_t{
		int from, to;
		T cost;
		Edge_t &inplace_flip(){
			swap(from, to);
			return *this;
		}
		Edge_t flip() const{
			return (*this).inplace_flip();
		}
	};
	int n;
	vector<Edge_t> edge;
	vector<vector<int>> adj;
	function<bool(int)> ignore;
	graph(int n = 1): n(n), adj(n){
		assert(n >= 1);
	}
	graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
		assert(n >= 1);
		if(undirected){
			for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);
		}
		else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);
	}
	graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
		assert(n >= 1);
		if(undirected){
			for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);
		}
		else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);
	}
	graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){
		assert(n >= 1);
		for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);
	}
	graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){
		assert(n >= 1);
		for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);
	}
	int add_vertex(){
		adj.emplace_back();
		return n ++;
	}
	int operator()(int u, int id) const{
		#ifdef LOCAL
		assert(0 <= id && id < (int)edge.size());
		assert(edge[id].from == u || edge[id].to == u);
		#endif
		return u ^ edge[id].from ^ edge[id].to;
	}
	int link(int u, int v, T w = {}){ // insert an undirected edge
		int id = (int)edge.size();
		adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});
		return id;
	}
	int orient(int u, int v, T w = {}){ // insert a directed edge
		int id = (int)edge.size();
		adj[u].push_back(id), edge.push_back({u, v, w});
		return id;
	}
	vector<int> neighbor(int u, int exclude = -1) const{
		vector<int> res;
		for(auto id: adj[u]){
			if(id == exclude || ignore && ignore(id)) continue;
			res.push_back(operator()(u, id));
		}
		return res;
	}
	vector<pair<int, T>> weighted_neighbor(int u, int exclude = -1) const{
		vector<pair<int, T>> res;
		for(auto id: adj[u]){
			if(id == exclude || ignore && ignore(id)) continue;
			res.push_back({operator()(u, id), edge[id].cost});
		}
		return res;
	}
	void clear(){
		for(auto [u, v, w]: edge){
			adj[u].clear();
			adj[v].clear();
		}
		edge.clear();
		ignore = {};
	}
	graph transpose() const{ // the transpose of the directed graph
		graph res(n);
		for(auto id = 0; id < (int)edge.size(); ++ id){
			if(ignore && ignore(id)) continue;
			res.orient(edge[id].to, edge[id].from, edge[id].cost);
		}
		return res;
	}
	int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)
		return (int)adj[u].size();
	}
	// The adjacency list is sorted for each vertex.
	vector<vector<int>> get_adjacency_list() const{
		vector<vector<int>> res(n);
		for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){
			if(ignore && ignore(id)) continue;
			res[(*this)(u, id)].push_back(u);
		}
		return res;
	}
	void set_ignoration_rule(const function<bool(int)> &f){
		ignore = f;
	}
	void reset_ignoration_rule(){
		ignore = nullptr;
	}
	friend ostream &operator<<(ostream &out, const graph &g){
		for(auto id = 0; id < (int)g.edge.size(); ++ id){
			if(g.ignore && g.ignore(id)) continue;
			auto &e = g.edge[id];
			out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";
		}
		return out;
	}
};

// Requires graph
template<class T, int level>
struct dfs_forest{
	static_assert(0 <= level && level <= 2);
	int n;
	vector<int> pv;
	vector<int> pe;
	vector<int> order;
	vector<int> pos;
	vector<int> end;
	vector<int> size;
	vector<int> depth;
	vector<int> root_of;
	vector<int> root;
	vector<T> dist;
	vector<int> min_depth;
	vector<int> min_depth_origin;
	vector<int> min_depth_spanning_edge;
	// extra_edge[u]: adjacent edges of u which is not part of the spanning forest found during the last dfs-like run.
	vector<vector<int>> extra_edge;
	vector<int> was;
	void init(int n){
		this->n = n;
		pv.resize(n, -1);
		pe.resize(n, -1);
		if constexpr(level >= 2) for(auto u: order){
			extra_edge[u].clear();
			extra_edge[u].shrink_to_fit();
		}
		order.clear();
		pos.resize(n, -1);
		end.resize(n, -1);
		size.resize(n, 0);
		depth.resize(n, -1);
		if constexpr(level >= 1){
			root_of.resize(n, -1);
			root.clear();
			dist.resize(n);
		}
		if constexpr(level >= 2){
			min_depth.resize(n, -1);
			min_depth_origin.resize(n, -1);
			min_depth_spanning_edge.resize(n, -1);
			extra_edge.resize(n, {});
		}
		was.resize(n, -2);
	}
	int attempt = -1;
	// O(# of nodes reachable from u)
	template<class U, class F>
	void _dfs(const graph<U> &g, int u, F UT, T base_dist){
		depth[u] = 0;
		pv[u] = pe[u] = -1;
		if constexpr(level >= 1){
			dist[u] = base_dist;
			root_of[u] = u;
			root.push_back(u);
		}
		auto recurse = [&](auto self, int u)->void{
			was[u] = attempt;
			pos[u] = (int)order.size();
			order.push_back(u);
			size[u] = 1;
			if constexpr(level >= 2){
				min_depth[u] = depth[u];
				min_depth_origin[u] = u;
				min_depth_spanning_edge[u] = -1;
				extra_edge[u].clear();
			}
			for(auto id: g.adj[u]){
				if(id == pe[u] || g.ignore && g.ignore(id)) continue;
				int v = g(u, id);
				if(was[v] == attempt){
					if constexpr(level >= 2){
						if(min_depth[u] > depth[v]){
							min_depth[u] = depth[v];
							min_depth_spanning_edge[u] = id;
						}
						if(pe[v] != id) extra_edge[u].push_back(id);
					}
					continue;
				}
				depth[v] = depth[u] + 1;
				pv[v] = u;
				pe[v] = id;
				if constexpr(level >= 1){
					dist[v] = UT(g.edge[id].cost, dist[u]);
					root_of[v] = root_of[u];
				}
				self(self, v);
				size[u] += size[v];
				if constexpr(level >= 2) if(min_depth[u] > min_depth[v]){
					min_depth[u] = min_depth[v];
					min_depth_origin[u] = min_depth_origin[v];
					min_depth_spanning_edge[u] = min_depth_spanning_edge[v];
				}
			}
			end[u] = (int)order.size();
		};
		recurse(recurse, u);
	}
	// O(# of nodes reachable from src)
	template<class U, class F = plus<>>
	void dfs(const graph<U> &g, const vector<int> &src, F UT = plus<>(), T base_dist = T{}){
		init(g.n);
		++ attempt;
		for(auto u: src){
			assert(0 <= u && u < n);
			if(was[u] != attempt) _dfs(g, u, UT, base_dist);
		}
	}
	// O(n + m)
	template<class U, class F = plus<>>
	void dfs_all(const graph<U> &g, F UT = plus<>(), T base_dist = T{}){
		init(g.n);
		++ attempt;
		for(auto u = 0; u < n; ++ u) if(was[u] != attempt) _dfs(g, u, UT, base_dist);
	}
	// Check if u is visited during the last dfs-like call.
	bool visited(int u) const{
		assert(0 <= u && u < n);
		return was[u] == attempt;
	}
	// Check if u is an ancestor of v in some spanning tree.
	bool ancestor_of(int u, int v) const{
		assert(visited(u) && visited(v));
		return pos[u] <= pos[v] && end[v] <= end[u];
	}
	vector<int> get_path(int u, int v) const{
		assert(visited(u) && visited(v));
		vector<int> left, right;
		while(u != v && ~pv[u] && ~pv[v]){
			if(depth[u] >= depth[v]){
				left.push_back(u);
				u = pv[u];
			}
			else{
				right.push_back(v);
				v = pv[v];
			}
		}
		assert(u == v);
		left.push_back(u);
		left.insert(left.end(), right.rbegin(), right.rend());
		return left;
	}
	// Check if any cycle is found during the last dfs-like call.
	// If must_contain_root = true, the sought cycle is forced to contain one of the root of the trees.
	template<class U>
	optional<pair<int, vector<int>>> find_any_cycle(const graph<U> &g, bool must_contain_root = false) const{
		static_assert(level >= 2);
		for(auto u: order) for(auto id: extra_edge[u]){
			int v = g(u, id);
			if(!ancestor_of(v, u) || must_contain_root && root_of[v] != v) continue;
			vector<int> cycle_edge;
			while(u != v) cycle_edge.push_back(pe[u]), u = pv[u];
			reverse(cycle_edge.begin(), cycle_edge.end());
			cycle_edge.push_back(id);
			return pair{v, cycle_edge};
		}
		return {};
	}
};

// pv, pe, order, pos, end, size, depth
template<class T>
auto make_basic_dfs_forest(){
	return dfs_forest<T, 0>();
}
// (basic_set), root_of, root, dist
template<class T>
auto make_augmented_dfs_forest(){
	return dfs_forest<T, 1>();
}
// (augmented_set), min_depth, min_depth_origin, min_depth_spanning_edge, extra_edge
template<class T>
auto make_full_dfs_forest(){
	return dfs_forest<T, 2>();
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n;
	cin >> n;
	vector<int> a(n);
	copy_n(istream_iterator<int>(cin), n, a.begin());
	set<pair<int, int>> s{{a[0], 0}};
	graph<int> g(n);
	for(auto [i, x]: a | ranges::views::enumerate | ranges::views::drop(1)){
		auto it = s.lower_bound({x, i});
		if(it == s.begin() || it != s.end() && prev(it)->second < it->second){
			g.orient(it->second, i);
		}
		else{
			g.orient(prev(it)->second, i);
		}
		s.insert(it, {x, i});
	}
	auto df = make_basic_dfs_forest<int>();
	df.dfs(g, {0});
	for(auto u = 0; u < n; ++ u){
		cout << df.depth[u] << " ";
	}
	cout << "\n";
	for(auto u = 0; u < n; ++ u){
		cout << df.size[u] - 1 << " ";
	}
	cout << "\n";
	return 0;
}

/*

*/