#279292 (C++14) No.399 動的な領主

提出ソース

結果

問題	No.399 動的な領主
ユーザー	noshi91
提出日時	2018-08-21 16:23:46
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	240 ms / 2,000 ms
コード長	7,242 bytes
コンパイル時間	700 ms
コンパイル使用メモリ	65,424 KB
実行使用メモリ	9,984 KB
最終ジャッジ日時	2024-05-09 11:36:13
合計ジャッジ時間	3,741 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	14 ms 5,376 KB
testcase_06	AC	240 ms 9,856 KB
testcase_07	AC	240 ms 9,856 KB
testcase_08	AC	228 ms 9,856 KB
testcase_09	AC	226 ms 9,856 KB
testcase_10	AC	4 ms 5,376 KB
testcase_11	AC	10 ms 5,376 KB
testcase_12	AC	133 ms 9,856 KB
testcase_13	AC	128 ms 9,856 KB
testcase_14	AC	47 ms 9,856 KB
testcase_15	AC	105 ms 9,856 KB
testcase_16	AC	121 ms 9,856 KB
testcase_17	AC	228 ms 9,984 KB
testcase_18	AC	229 ms 9,856 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cassert>
#include <cstddef>
#include <memory>
#include <utility>
#include <vector>

template <class ValueMonoid, class OperatorMonoid, class Modifier>
class lazy_st_trees {
public:
	using value_structure = ValueMonoid;
	using value_type = typename value_structure::value_type;
	using operator_structure = OperatorMonoid;
	using operator_type = typename operator_structure::value_type;
	using modifier = Modifier;
	using size_type = ::std::size_t;

private:
	class node_type {
	public:
		node_type *left, *right, *parent;
		typename lazy_st_trees::value_type value, sum;
		typename lazy_st_trees::operator_type lazy;
		bool reversed; // reverse->lazy
		template <class V>
		node_type(node_type *p, V &&v, operator_type &&o)
			: left(p), right(p), parent(p), value(::std::forward<V>(v)), sum(value),
			lazy(::std::move(o)), reversed(0) {}
	};

	using pointer = node_type *;
	using const_pointer = const node_type *;

	static void reverse(const pointer ptr) {
		ptr->lazy = operator_structure::reverse(ptr->lazy);
		ptr->reversed ^= 1;
	}
	static void push(const pointer ptr) {
		if (ptr->reversed) {
			ptr->reversed = 0;
			ptr->value = value_structure::reverse(ptr->value);
			::std::swap(ptr->left, ptr->right);
			reverse(ptr->left);
			reverse(ptr->right);
		}
		ptr->left->lazy = operator_structure::operation(ptr->left->lazy, ptr->lazy);
		ptr->right->lazy =
			operator_structure::operation(ptr->right->lazy, ptr->lazy);
		ptr->value = modifier::operation(ptr->value, ptr->lazy);
		ptr->lazy = operator_structure::identity();
	}
	void propagate(pointer ptr) {
		pointer prev = nullptr;
		while (ptr != nil()) {
			::std::swap(ptr->parent, prev);
			::std::swap(ptr, prev);
		}
		while (prev) {
			push(prev);
			::std::swap(prev->parent, ptr);
			::std::swap(prev, ptr);
		}
		nodes.back().sum = value_structure::identity();
		nodes.back().lazy = operator_structure::identity();
		nodes.back().reversed = 0;
	}
	static value_type reflect(const const_pointer ptr) {
		return modifier::operation(
			ptr->reversed ? value_structure::reverse(ptr->sum) : ptr->sum,
			ptr->lazy);
	}
	static void calc(const pointer ptr) {
		ptr->sum = value_structure::operation(
			value_structure::operation(reflect(ptr->left), ptr->value),
			reflect(ptr->right));
	}
	static void rotate_l(const pointer ptr, const pointer ch) {
		ptr->right = ch->left;
		ch->left->parent = ptr;
		calc(ptr);
		ch->left = ptr;
		ptr->parent = ch;
	}
	static void rotate_r(const pointer ptr, const pointer ch) {
		ptr->left = ch->right;
		ch->right->parent = ptr;
		calc(ptr);
		ch->right = ptr;
		ptr->parent = ch;
	}
	static void splay(const pointer ptr) {
		for (pointer x, y = ptr;;) {
			x = ptr->parent;
			if (x->left == y) {
				y = x->parent;
				ptr->parent = y->parent;
				if (y->left == x)
					rotate_r(y, x), rotate_r(x, ptr);
				else if (y->right == x)
					rotate_l(y, ptr), rotate_r(x, ptr);
				else
					return ptr->parent = y, rotate_r(x, ptr);
			}
			else if (x->right == y) {
				y = x->parent;
				ptr->parent = y->parent;
				if (y->right == x)
					rotate_l(y, x), rotate_l(x, ptr);
				else if (y->left == x)
					rotate_r(y, ptr), rotate_l(x, ptr);
				else
					return ptr->parent = y, rotate_l(x, ptr);
			}
			else {
				return;
			}
		}
	}
	void expose(const pointer ptr) {
		propagate(ptr);
		pointer x = ptr, prev = nil();
		while (x != nil()) {
			splay(x);
			x->right = prev;
			calc(x);
			prev = x;
			x = x->parent;
		}
		splay(ptr);
		calc(ptr);
	}
	void reroot(const pointer ptr) {
		expose(ptr);
		reverse(ptr);
	}

	::std::vector<node_type> nodes;

	pointer get_ptr(const size_type v) { return nodes.data() + v; }
	pointer nil() { return &nodes.back(); }

public:
	lazy_st_trees() : nodes() {}
	explicit lazy_st_trees(const size_type size) : nodes() {
		nodes.reserve(size + 1);
		nodes.resize(size + 1, { nodes.data() + size, value_structure::identity(),
			operator_structure::identity() });
	}
	template <class InputIter> lazy_st_trees(InputIter first, InputIter last) {
		const size_type size = ::std::distance(first, last);
		nodes.reserve(size + 1);
		pointer p = nodes.data() + size;
		for (; first != last; ++first)
			nodes.emplace_back(p, *first, operator_structure::identity());
	}

	bool empty() const { return size() == 0; }
	size_type size() const { return nodes.size() - 1; }

	bool connected(const size_type v, const size_type u) {
		assert(v < size());
		assert(u < size());
		expose(get_ptr(v));
		expose(get_ptr(u));
		return nodes[v].parent != nil() || v == u;
	}
	value_type fold(const size_type v, const size_type u) {
		assert(v < size());
		assert(u < size());
		assert(connected(v, u));
		reroot(get_ptr(v));
		expose(get_ptr(u));
		return nodes[u].sum;
	}

	void link(const size_type parent, const size_type child) {
		assert(parent < size());
		assert(child < size());
		assert(!connected(parent, child));
		reroot(get_ptr(child));
		nodes[child].parent = get_ptr(parent);
	}
	void cut(const size_type v) {
		assert(v < size());
		expose(get_ptr(v));
		nodes[v].left->parent = nil();
		nodes[v].left = nil();
		nodes[v].sum = nodes[v].value;
	}
	void update(const size_type v, const size_type u, const operator_type &data) {
		assert(v < size());
		assert(u < size());
		assert(connected(v, u));
		reroot(get_ptr(v));
		expose(get_ptr(u));
		nodes[u].lazy = data;
	}
	template <class F> void update(const size_type v, const F &f) {
		assert(v < size());
		expose(get_ptr(v));
		nodes[v].value = f(nodes[v].value);
		calc(get_ptr(v));
	}
};

#include <cstddef>
#include <utility>
template <class T, class Size = ::std::size_t> class sum_monoid {
public:
	using size_type = Size;
	using value_type = ::std::pair<T, size_type>;
	static T get(const value_type &x) { return x.first; }
	static value_type operation(const value_type &x, const value_type &y) {
		return value_type(x.first + y.first, x.second + y.second);
	}
	static value_type identity() { return value_type(T(0), size_type(0)); }
	static value_type reverse(const value_type &x) { return x; }
};

template <class T> class plus_monoid {
public:
	using value_type = T;
	static value_type operation(const value_type &x, const value_type &y) {
		return x + y;
	}
	static value_type identity() { return value_type(0); }
	static value_type reverse(const value_type &x) { return x; }
};

template <class T, class Size = ::std::size_t> class sum_plus {
public:
	static ::std::pair<T, Size> operation(const ::std::pair<T, Size> &x,
		const T &y) {
		return ::std::pair<T, Size>(x.first + y * x.second, x.second);
	}
};

#include<cstdio>
using u32 = unsigned int;

void scan(u32 &d) {
	d = 0;
	int c;
	while (c = fgetc(stdin), c == '\n' || c == ' ');
	do
		d = d * 10 + c - '0';
	while (c = fgetc(stdin), c != '\n' && c != ' ');
}

int main() {
	using u64 = unsigned long long;

	u32 n;
	scan(n);

	lazy_st_trees<sum_monoid<u64>,
		plus_monoid<u64>,
		sum_plus<u64>> st(n);

	using tp = sum_monoid<u64>::value_type;
	for (int i = 0;i < n;++i)
		st.update(i, [](tp) {return tp(1, 1);});

	u32 u, v;
	while (--n) {
		scan(u);
		scan(v);
		st.link(u - 1, v - 1);
	}

	scan(n);

	u64 ans = 0;

	while (n--) {
		scan(u);
		scan(v);
		ans += st.fold(u - 1, v - 1).first;
		st.update(u - 1, v - 1, 1);
	}

	printf("%llu\n", ans);

	return 0;
}

yukicoder

結果

テストケース

ソースコード