Lazy Reversible Treap（遅延伝搬・反転可能乱択平衡二分木）

data_structure/lazy_reversible_treap.hpp · GitHub で見る

共通ページ

#include "lib/data_structure/lazy_reversible_treap.hpp"
#include "lib/math/mint.hpp"

struct F { mint a, b; };
mint op(mint a, mint b) { return a + b; }
mint e() { return 0; }
mint mapping(F f, mint x, int n) { return f.a * x + f.b * n; }
F composition(F f, F g) { return {f.a * g.a, f.a * g.b + f.b}; }
F id() { return {1, 0}; }

using Tree = LazyReversibleTreap<mint, op, e, F, mapping, composition, id, true>;
Tree tree(std::vector<mint>{1, 2, 3});
tree.insert(1, 10);
tree.apply(0, 3, {2, 1});
tree.reverse(1, 4);
auto sum = tree.prod(0, 3);

添字は 0 始まり、区間は \([l,r)\) です。引数なしで空列、Tree(vector<S>, seed = 0) で初期列を構築します。Tree(seed) は空列の乱数シードを指定します。

op は結合的な演算、e() は単位元です。mapping(f,x,n) は長さ \(n\) の積 \(x\) に更新 \(f\) を適用し、各要素への同じ更新と整合する必要があります。composition(f,g) は \(g\) の後に \(f\) を適用する更新、id() は恒等更新です。

最後のテンプレート引数は、op が可換な場合のみ true にします。既定の false では逆順の積も保持し、非可換な演算に対応します。

操作	内容・返り値	計算量
`Tree(seed = 0)` / `Tree(a,seed = 0)`	空／配列から構築。`Tree` はテンプレート引数を指定した型	空: \(O(1)\)、配列: \(O(n)\)
`insert(p,x)`	位置 `p` の直前に挿入	期待 \(O(\log n)\)
`erase(p)`	要素を削除し、その値を返す	期待 \(O(\log n)\)
`get(p)` / `set(p,x)`	1 点の取得／代入	期待 \(O(\log n)\)
`apply(p,f)` / `apply(l,r,f)`	1 点／区間に更新を適用	期待 \(O(\log n)\)
`reverse(l,r)`	区間を反転	期待 \(O(\log n)\)
`prod(l,r)` / `all_prod()`	区間／全体の集約	prod: 期待 \(O(\log n)\)、all_prod: \(O(1)\)
`rotate(l,m,r)`	\([l,m)\) と \([m,r)\) を入れ替える	期待 \(O(\log n)\)
`move(l,r,p)`	区間を切り取り、削除後の位置 `p` の直前へ挿入	期待 \(O(\log n)\)
`to_vector()`	全要素を取得	\(O(n)\)
`size()` / `empty()`	要素数／空判定	\(O(1)\)
`assign(a)` / `clear()`	配列で再構築／容量を残して空にする	assign: \(O(m+n)\)、clear: \(O(m)\)
`reserve(n)` / `memory_usage()`	ノード領域を予約／確保済み領域のバイト数	reserve: \(O(m)\)、memory_usage: \(O(1)\)
`swap(other)`	内容と乱数生成器の状態を交換	\(O(1)\)

要素数と予約容量は \(2^{30}\) 未満です。削除したノードは再利用します。clear() は確保容量を残します。

現在の要素数を \(n\)、最大要素数を \(m\) とすると、構築は \(O(n)\)、assign は \(O(m+n)\)、挿入・削除・1 点操作・区間操作は期待 \(O(\log n)\)、all_prod・size・empty・memory_usage は \(O(1)\)、to_vector は \(O(n)\)、reserve・clear は \(O(m)\) です。空間は \(O(m)\)（予約容量が大きい場合はその容量分）です。演算・更新・値のコピーを \(O(1)\) とします。

依存ライブラリ

SplitMix64

検証コード

コード

#line 1 "data_structure/lazy_reversible_treap.hpp"

#line 1 "components/splitmix64.hpp"

#include <cstdint>

inline std::uint64_t splitmix64(std::uint64_t x) {
	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
	x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
	return x ^ (x >> 31);
}
class SplitMix64 {
	std::uint64_t state;

public:
	explicit SplitMix64(std::uint64_t seed = 0) : state(seed) {}
	std::uint64_t operator()() { return splitmix64(state += 0x9e3779b97f4a7c15ULL); }
};

#line 5 "data_structure/lazy_reversible_treap.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#line 9 "data_structure/lazy_reversible_treap.hpp"
#include <type_traits>
#include <utility>
#include <vector>

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC push_options
#pragma GCC optimize("O3")
#endif

template <class S, auto op, auto e, class F, auto mapping, auto composition, auto id, bool commutative = false>
class LazyReversibleTreap {
	struct Empty {};
	using Back = std::conditional_t<commutative, Empty, S>;
	struct Node {
		int left = 0, right = 0;
		std::uint32_t count : 30 = 1;
		std::uint32_t pending : 1 = 0;
		std::uint32_t reversed : 1 = 0;
		std::uint32_t priority;
		S value, product;
		[[no_unique_address]] Back back;
		F lazy = id();
		static Back make_back(const S &value) {
			if constexpr (commutative) return {};
			else return value;
		}
		Node(S value, std::uint32_t priority) : priority(priority), value(std::move(value)), product(this->value), back(make_back(this->value)) {}
	};
	std::vector<Node> t;
	SplitMix64 rng;
	int root = 0, free = 0;
	bool lazy_applied = false;
	int count(int x) const { return t[x].count; }
	template <bool resize = true>
	void pull(int x) {
		auto &v = t[x];
		int l = v.left, r = v.right;
		if constexpr (resize) v.count = count(l) + count(r) + 1;
		v.product = l ? op(t[l].product, v.value) : v.value;
		if (r) v.product = op(std::move(v.product), t[r].product);
		if constexpr (!commutative) {
			v.back = r ? op(t[r].back, v.value) : v.value;
			if (l) v.back = op(std::move(v.back), t[l].back);
		}
	}
	void flip(int x) {
		if (!x || count(x) == 1) return;
		auto &v = t[x];
		std::swap(v.left, v.right);
		if constexpr (!commutative) std::swap(v.product, v.back);
		v.reversed ^= 1;
	}
	void act(int x, const F &f) {
		if (!x) return;
		auto &v = t[x];
		if (count(x) == 1) {
			v.value = v.product = mapping(f, v.product, 1);
			if constexpr (!commutative) v.back = v.product;
			return;
		}
		v.product = mapping(f, v.product, count(x));
		if constexpr (!commutative) v.back = mapping(f, v.back, count(x));
		v.lazy = v.pending ? composition(f, v.lazy) : f;
		v.pending = true;
	}
	void push(int x) {
		auto &v = t[x];
		if (v.reversed) {
			flip(v.left);
			flip(v.right);
			v.reversed = 0;
		}
		if (v.pending) {
			v.value = mapping(v.lazy, v.value, 1);
			act(v.left, v.lazy);
			act(v.right, v.lazy);
			v.pending = false;
		}
	}
	int make(S value) {
		if (free) {
			int x = free;
			free = t[x].left;
			t[x] = Node(std::move(value), std::uint32_t(rng()));
			return x;
		}
		assert(t.size() <= (std::size_t(1) << 30) - 1);
		t.emplace_back(std::move(value), std::uint32_t(rng()));
		return int(t.size()) - 1;
	}
	std::pair<int, int> split(int x, int k) {
		if (!x) return {0, 0};
		if (!k) return {0, x};
		if (k == count(x)) return {x, 0};
		push(x);
		int left = count(t[x].left);
		if (k <= left) {
			auto [a, b] = split(t[x].left, k);
			t[x].left = b;
			pull(x);
			return {a, x};
		}
		auto [a, b] = split(t[x].right, k - left - 1);
		t[x].right = a;
		pull(x);
		return {x, b};
	}
	int merge(int a, int b) {
		if (!a || !b) return a | b;
		if (t[a].priority > t[b].priority) {
			push(a);
			t[a].right = merge(t[a].right, b);
			pull(a);
			return a;
		}
		push(b);
		t[b].left = merge(a, t[b].left);
		pull(b);
		return b;
	}
	int insert_node(int x, int p, int added) {
		if (!x) return added;
		if (t[added].priority >= t[x].priority) {
			auto [a, b] = split(x, p);
			t[added].left = a;
			t[added].right = b;
			pull(added);
			return added;
		}
		push(x);
		int left = count(t[x].left);
		if (p <= left) t[x].left = insert_node(t[x].left, p, added);
		else t[x].right = insert_node(t[x].right, p - left - 1, added);
		pull(x);
		return x;
	}
	int erase_node(int x, int p, S &value) {
		push(x);
		int left = count(t[x].left);
		if (p == left) {
			value = std::move(t[x].value);
			int result = merge(t[x].left, t[x].right);
			t[x].left = free;
			free = x;
			return result;
		}
		if (p < left) t[x].left = erase_node(t[x].left, p, value);
		else t[x].right = erase_node(t[x].right, p - left - 1, value);
		pull(x);
		return x;
	}
	void set_node(int x, int p, S value) {
		push(x);
		int left = count(t[x].left);
		if (p == left) t[x].value = std::move(value);
		else if (p < left) set_node(t[x].left, p, std::move(value));
		else set_node(t[x].right, p - left - 1, std::move(value));
		pull<false>(x);
	}
	S fold(int x, int l, int r, bool reversed = false) const {
		for (;;) {
			const auto &v = t[x];
			if (!l && r == count(x)) {
				if constexpr (!commutative) if (reversed) return v.back;
				return v.product;
			}
			int a = reversed ? v.right : v.left, b = reversed ? v.left : v.right;
			int left = count(a);
			reversed ^= v.reversed;
			if (r <= left) { x = a; continue; }
			if (left < l) { x = b; l -= left + 1; r -= left + 1; continue; }
			S result = v.value;
			if (l < left) result = op(fold(a, l, left, reversed), std::move(result));
			if (left + 1 < r) result = op(std::move(result), fold(b, 0, r - left - 1, reversed));
			return result;
		}
	}
	S fold_lazy(int x, int l, int r, const F *carry = nullptr, bool reversed = false) const {
		const auto &v = t[x];
		if (!l && r == count(x)) {
			S result = v.product;
			if constexpr (!commutative) if (reversed) result = v.back;
			return carry ? mapping(*carry, std::move(result), count(x)) : result;
		}
		F combined = id();
		if (v.pending) {
			combined = carry ? composition(*carry, v.lazy) : v.lazy;
			carry = &combined;
		}
		int a = reversed ? v.right : v.left, b = reversed ? v.left : v.right;
		int left = count(a);
		reversed ^= v.reversed;
		if (r <= left) return fold_lazy(a, l, r, carry, reversed);
		if (left < l) return fold_lazy(b, l - left - 1, r - left - 1, carry, reversed);
		S result = carry ? mapping(*carry, v.value, 1) : v.value;
		if (l < left) result = op(fold_lazy(a, l, left, carry, reversed), std::move(result));
		if (left + 1 < r) result = op(std::move(result), fold_lazy(b, 0, r - left - 1, carry, reversed));
		return result;
	}
	void apply_node(int x, int l, int r, const F &f) {
		if (!l && r == count(x)) { act(x, f); return; }
		push(x);
		int left = count(t[x].left);
		if (l < left) apply_node(t[x].left, l, std::min(r, left), f);
		if (l <= left && left < r) t[x].value = mapping(f, t[x].value, 1);
		if (left + 1 < r) apply_node(t[x].right, std::max(l - left - 1, 0), r - left - 1, f);
		pull<false>(x);
	}
	int reverse_node(int x, int l, int r) {
		if (!l && r == count(x)) { flip(x); return x; }
		push(x);
		int left = count(t[x].left);
		if (r <= left) t[x].left = reverse_node(t[x].left, l, r);
		else if (left < l) t[x].right = reverse_node(t[x].right, l - left - 1, r - left - 1);
		else {
			auto [a, b] = split(t[x].left, l);
			auto [c, d] = split(t[x].right, r - left - 1);
			flip(b);
			flip(c);
			t[x].left = merge(a, c);
			t[x].right = merge(b, d);
		}
		if constexpr (!commutative) pull<false>(x);
		return x;
	}
	void collect(int x, std::vector<S> &values) {
		if (!x) return;
		push(x);
		collect(t[x].left, values);
		values.push_back(t[x].value);
		collect(t[x].right, values);
	}
	void bounds(int l, int r) const { assert(0 <= l && l <= r && r <= size()); (void)l; (void)r; }

public:
	using value_type = S;
	using action_type = F;
	explicit LazyReversibleTreap(std::uint64_t seed = 0) : rng(seed) { t.emplace_back(e(), 0); t[0].count = 0; }
	explicit LazyReversibleTreap(const std::vector<S> &values, std::uint64_t seed = 0) : LazyReversibleTreap(seed) { assign(values); }
	LazyReversibleTreap(const LazyReversibleTreap &) = default;
	LazyReversibleTreap &operator=(const LazyReversibleTreap &) = default;
	LazyReversibleTreap(LazyReversibleTreap &&other) : LazyReversibleTreap() { swap(other); }
	LazyReversibleTreap &operator=(LazyReversibleTreap &&other) {
		if (this != &other) { LazyReversibleTreap moved(std::move(other)); swap(moved); }
		return *this;
	}
	void swap(LazyReversibleTreap &other) noexcept {
		t.swap(other.t);
		std::swap(rng, other.rng);
		std::swap(root, other.root);
		std::swap(free, other.free);
		std::swap(lazy_applied, other.lazy_applied);
	}
	int size() const { return count(root); }
	bool empty() const { return !root; }
	void reserve(std::size_t n) { assert(n < (std::size_t(1) << 30)); t.reserve(n + 1); }
	std::size_t memory_usage() const { return t.capacity() * sizeof(Node); }
	void clear() { t.erase(t.begin() + 1, t.end()); root = free = 0; lazy_applied = false; }
	void assign(const std::vector<S> &values) {
		clear();
		reserve(values.size());
		std::vector<int> path;
		for (const S &value : values) {
			int x = make(value), last = 0;
			while (!path.empty() && t[path.back()].priority <= t[x].priority) {
				last = path.back(); path.pop_back(); pull(last);
			}
			t[x].left = last;
			if (!path.empty()) t[path.back()].right = x;
			path.push_back(x);
		}
		if (!path.empty()) root = path[0];
		while (!path.empty()) { pull(path.back()); path.pop_back(); }
	}
	void insert(int p, S value) { bounds(p, p); root = insert_node(root, p, make(std::move(value))); }
	S erase(int p) { bounds(p, p + 1); S value = e(); root = erase_node(root, p, value); return value; }
	S get(int p) {
		bounds(p, p + 1);
		int x = root;
		for (;;) {
			push(x);
			int left = count(t[x].left);
			if (p == left) return t[x].value;
			if (p < left) x = t[x].left;
			else p -= left + 1, x = t[x].right;
		}
	}
	void set(int p, S value) { bounds(p, p + 1); set_node(root, p, std::move(value)); }
	S prod(int l, int r) { bounds(l, r); return l == r ? e() : lazy_applied ? fold_lazy(root, l, r) : fold(root, l, r); }
	S all_prod() const { return t[root].product; }
	void apply(int p, const F &f) { apply(p, p + 1, f); }
	void apply(int l, int r, const F &f) { bounds(l, r); if (l != r) { lazy_applied = true; apply_node(root, l, r, f); } }
	void reverse(int l, int r) { bounds(l, r); if (r - l > 1) root = reverse_node(root, l, r); }
	void rotate(int l, int m, int r) {
		bounds(l, m); bounds(m, r);
		if (l == m || m == r) return;
		auto [a, b] = split(root, l);
		auto [c, d] = split(b, m - l);
		auto [f, g] = split(d, r - m);
		root = merge(a, merge(f, merge(c, g)));
	}
	void move(int l, int r, int p) {
		bounds(l, r);
		assert(0 <= p && p <= size() - (r - l));
		if (l == r || l == p) return;
		auto [a, b] = split(root, l);
		auto [c, d] = split(b, r - l);
		auto [f, g] = split(merge(a, d), p);
		root = merge(f, merge(c, g));
	}
	std::vector<S> to_vector() { std::vector<S> values; values.reserve(size()); collect(root, values); return values; }
};

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC pop_options
#endif

#ifndef LAZY_REVERSIBLE_TREAP_HPP
#define LAZY_REVERSIBLE_TREAP_HPP

#include "../components/splitmix64.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <utility>
#include <vector>

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC push_options
#pragma GCC optimize("O3")
#endif

template <class S, auto op, auto e, class F, auto mapping, auto composition, auto id, bool commutative = false>
class LazyReversibleTreap {
	struct Empty {};
	using Back = std::conditional_t<commutative, Empty, S>;
	struct Node {
		int left = 0, right = 0;
		std::uint32_t count : 30 = 1;
		std::uint32_t pending : 1 = 0;
		std::uint32_t reversed : 1 = 0;
		std::uint32_t priority;
		S value, product;
		[[no_unique_address]] Back back;
		F lazy = id();
		static Back make_back(const S &value) {
			if constexpr (commutative) return {};
			else return value;
		}
		Node(S value, std::uint32_t priority) : priority(priority), value(std::move(value)), product(this->value), back(make_back(this->value)) {}
	};
	std::vector<Node> t;
	SplitMix64 rng;
	int root = 0, free = 0;
	bool lazy_applied = false;
	int count(int x) const { return t[x].count; }
	template <bool resize = true>
	void pull(int x) {
		auto &v = t[x];
		int l = v.left, r = v.right;
		if constexpr (resize) v.count = count(l) + count(r) + 1;
		v.product = l ? op(t[l].product, v.value) : v.value;
		if (r) v.product = op(std::move(v.product), t[r].product);
		if constexpr (!commutative) {
			v.back = r ? op(t[r].back, v.value) : v.value;
			if (l) v.back = op(std::move(v.back), t[l].back);
		}
	}
	void flip(int x) {
		if (!x || count(x) == 1) return;
		auto &v = t[x];
		std::swap(v.left, v.right);
		if constexpr (!commutative) std::swap(v.product, v.back);
		v.reversed ^= 1;
	}
	void act(int x, const F &f) {
		if (!x) return;
		auto &v = t[x];
		if (count(x) == 1) {
			v.value = v.product = mapping(f, v.product, 1);
			if constexpr (!commutative) v.back = v.product;
			return;
		}
		v.product = mapping(f, v.product, count(x));
		if constexpr (!commutative) v.back = mapping(f, v.back, count(x));
		v.lazy = v.pending ? composition(f, v.lazy) : f;
		v.pending = true;
	}
	void push(int x) {
		auto &v = t[x];
		if (v.reversed) {
			flip(v.left);
			flip(v.right);
			v.reversed = 0;
		}
		if (v.pending) {
			v.value = mapping(v.lazy, v.value, 1);
			act(v.left, v.lazy);
			act(v.right, v.lazy);
			v.pending = false;
		}
	}
	int make(S value) {
		if (free) {
			int x = free;
			free = t[x].left;
			t[x] = Node(std::move(value), std::uint32_t(rng()));
			return x;
		}
		assert(t.size() <= (std::size_t(1) << 30) - 1);
		t.emplace_back(std::move(value), std::uint32_t(rng()));
		return int(t.size()) - 1;
	}
	std::pair<int, int> split(int x, int k) {
		if (!x) return {0, 0};
		if (!k) return {0, x};
		if (k == count(x)) return {x, 0};
		push(x);
		int left = count(t[x].left);
		if (k <= left) {
			auto [a, b] = split(t[x].left, k);
			t[x].left = b;
			pull(x);
			return {a, x};
		}
		auto [a, b] = split(t[x].right, k - left - 1);
		t[x].right = a;
		pull(x);
		return {x, b};
	}
	int merge(int a, int b) {
		if (!a || !b) return a | b;
		if (t[a].priority > t[b].priority) {
			push(a);
			t[a].right = merge(t[a].right, b);
			pull(a);
			return a;
		}
		push(b);
		t[b].left = merge(a, t[b].left);
		pull(b);
		return b;
	}
	int insert_node(int x, int p, int added) {
		if (!x) return added;
		if (t[added].priority >= t[x].priority) {
			auto [a, b] = split(x, p);
			t[added].left = a;
			t[added].right = b;
			pull(added);
			return added;
		}
		push(x);
		int left = count(t[x].left);
		if (p <= left) t[x].left = insert_node(t[x].left, p, added);
		else t[x].right = insert_node(t[x].right, p - left - 1, added);
		pull(x);
		return x;
	}
	int erase_node(int x, int p, S &value) {
		push(x);
		int left = count(t[x].left);
		if (p == left) {
			value = std::move(t[x].value);
			int result = merge(t[x].left, t[x].right);
			t[x].left = free;
			free = x;
			return result;
		}
		if (p < left) t[x].left = erase_node(t[x].left, p, value);
		else t[x].right = erase_node(t[x].right, p - left - 1, value);
		pull(x);
		return x;
	}
	void set_node(int x, int p, S value) {
		push(x);
		int left = count(t[x].left);
		if (p == left) t[x].value = std::move(value);
		else if (p < left) set_node(t[x].left, p, std::move(value));
		else set_node(t[x].right, p - left - 1, std::move(value));
		pull<false>(x);
	}
	S fold(int x, int l, int r, bool reversed = false) const {
		for (;;) {
			const auto &v = t[x];
			if (!l && r == count(x)) {
				if constexpr (!commutative) if (reversed) return v.back;
				return v.product;
			}
			int a = reversed ? v.right : v.left, b = reversed ? v.left : v.right;
			int left = count(a);
			reversed ^= v.reversed;
			if (r <= left) { x = a; continue; }
			if (left < l) { x = b; l -= left + 1; r -= left + 1; continue; }
			S result = v.value;
			if (l < left) result = op(fold(a, l, left, reversed), std::move(result));
			if (left + 1 < r) result = op(std::move(result), fold(b, 0, r - left - 1, reversed));
			return result;
		}
	}
	S fold_lazy(int x, int l, int r, const F *carry = nullptr, bool reversed = false) const {
		const auto &v = t[x];
		if (!l && r == count(x)) {
			S result = v.product;
			if constexpr (!commutative) if (reversed) result = v.back;
			return carry ? mapping(*carry, std::move(result), count(x)) : result;
		}
		F combined = id();
		if (v.pending) {
			combined = carry ? composition(*carry, v.lazy) : v.lazy;
			carry = &combined;
		}
		int a = reversed ? v.right : v.left, b = reversed ? v.left : v.right;
		int left = count(a);
		reversed ^= v.reversed;
		if (r <= left) return fold_lazy(a, l, r, carry, reversed);
		if (left < l) return fold_lazy(b, l - left - 1, r - left - 1, carry, reversed);
		S result = carry ? mapping(*carry, v.value, 1) : v.value;
		if (l < left) result = op(fold_lazy(a, l, left, carry, reversed), std::move(result));
		if (left + 1 < r) result = op(std::move(result), fold_lazy(b, 0, r - left - 1, carry, reversed));
		return result;
	}
	void apply_node(int x, int l, int r, const F &f) {
		if (!l && r == count(x)) { act(x, f); return; }
		push(x);
		int left = count(t[x].left);
		if (l < left) apply_node(t[x].left, l, std::min(r, left), f);
		if (l <= left && left < r) t[x].value = mapping(f, t[x].value, 1);
		if (left + 1 < r) apply_node(t[x].right, std::max(l - left - 1, 0), r - left - 1, f);
		pull<false>(x);
	}
	int reverse_node(int x, int l, int r) {
		if (!l && r == count(x)) { flip(x); return x; }
		push(x);
		int left = count(t[x].left);
		if (r <= left) t[x].left = reverse_node(t[x].left, l, r);
		else if (left < l) t[x].right = reverse_node(t[x].right, l - left - 1, r - left - 1);
		else {
			auto [a, b] = split(t[x].left, l);
			auto [c, d] = split(t[x].right, r - left - 1);
			flip(b);
			flip(c);
			t[x].left = merge(a, c);
			t[x].right = merge(b, d);
		}
		if constexpr (!commutative) pull<false>(x);
		return x;
	}
	void collect(int x, std::vector<S> &values) {
		if (!x) return;
		push(x);
		collect(t[x].left, values);
		values.push_back(t[x].value);
		collect(t[x].right, values);
	}
	void bounds(int l, int r) const { assert(0 <= l && l <= r && r <= size()); (void)l; (void)r; }

  public:
	using value_type = S;
	using action_type = F;
	explicit LazyReversibleTreap(std::uint64_t seed = 0) : rng(seed) { t.emplace_back(e(), 0); t[0].count = 0; }
	explicit LazyReversibleTreap(const std::vector<S> &values, std::uint64_t seed = 0) : LazyReversibleTreap(seed) { assign(values); }
	LazyReversibleTreap(const LazyReversibleTreap &) = default;
	LazyReversibleTreap &operator=(const LazyReversibleTreap &) = default;
	LazyReversibleTreap(LazyReversibleTreap &&other) : LazyReversibleTreap() { swap(other); }
	LazyReversibleTreap &operator=(LazyReversibleTreap &&other) {
		if (this != &other) { LazyReversibleTreap moved(std::move(other)); swap(moved); }
		return *this;
	}
	void swap(LazyReversibleTreap &other) noexcept {
		t.swap(other.t);
		std::swap(rng, other.rng);
		std::swap(root, other.root);
		std::swap(free, other.free);
		std::swap(lazy_applied, other.lazy_applied);
	}
	int size() const { return count(root); }
	bool empty() const { return !root; }
	void reserve(std::size_t n) { assert(n < (std::size_t(1) << 30)); t.reserve(n + 1); }
	std::size_t memory_usage() const { return t.capacity() * sizeof(Node); }
	void clear() { t.erase(t.begin() + 1, t.end()); root = free = 0; lazy_applied = false; }
	void assign(const std::vector<S> &values) {
		clear();
		reserve(values.size());
		std::vector<int> path;
		for (const S &value : values) {
			int x = make(value), last = 0;
			while (!path.empty() && t[path.back()].priority <= t[x].priority) {
				last = path.back(); path.pop_back(); pull(last);
			}
			t[x].left = last;
			if (!path.empty()) t[path.back()].right = x;
			path.push_back(x);
		}
		if (!path.empty()) root = path[0];
		while (!path.empty()) { pull(path.back()); path.pop_back(); }
	}
	void insert(int p, S value) { bounds(p, p); root = insert_node(root, p, make(std::move(value))); }
	S erase(int p) { bounds(p, p + 1); S value = e(); root = erase_node(root, p, value); return value; }
	S get(int p) {
		bounds(p, p + 1);
		int x = root;
		for (;;) {
			push(x);
			int left = count(t[x].left);
			if (p == left) return t[x].value;
			if (p < left) x = t[x].left;
			else p -= left + 1, x = t[x].right;
		}
	}
	void set(int p, S value) { bounds(p, p + 1); set_node(root, p, std::move(value)); }
	S prod(int l, int r) { bounds(l, r); return l == r ? e() : lazy_applied ? fold_lazy(root, l, r) : fold(root, l, r); }
	S all_prod() const { return t[root].product; }
	void apply(int p, const F &f) { apply(p, p + 1, f); }
	void apply(int l, int r, const F &f) { bounds(l, r); if (l != r) { lazy_applied = true; apply_node(root, l, r, f); } }
	void reverse(int l, int r) { bounds(l, r); if (r - l > 1) root = reverse_node(root, l, r); }
	void rotate(int l, int m, int r) {
		bounds(l, m); bounds(m, r);
		if (l == m || m == r) return;
		auto [a, b] = split(root, l);
		auto [c, d] = split(b, m - l);
		auto [f, g] = split(d, r - m);
		root = merge(a, merge(f, merge(c, g)));
	}
	void move(int l, int r, int p) {
		bounds(l, r);
		assert(0 <= p && p <= size() - (r - l));
		if (l == r || l == p) return;
		auto [a, b] = split(root, l);
		auto [c, d] = split(b, r - l);
		auto [f, g] = split(merge(a, d), p);
		root = merge(f, merge(c, g));
	}
	std::vector<S> to_vector() { std::vector<S> values; values.reserve(size()); collect(root, values); return values; }
};

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC pop_options
#endif

#endif

#line 1 "data_structure/lazy_reversible_treap.hpp"



#line 1 "components/splitmix64.hpp"



#include <cstdint>

inline std::uint64_t splitmix64(std::uint64_t x) {
	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
	x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
	return x ^ (x >> 31);
}
class SplitMix64 {
	std::uint64_t state;

  public:
	explicit SplitMix64(std::uint64_t seed = 0) : state(seed) {}
	std::uint64_t operator()() { return splitmix64(state += 0x9e3779b97f4a7c15ULL); }
};


#line 5 "data_structure/lazy_reversible_treap.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#line 9 "data_structure/lazy_reversible_treap.hpp"
#include <type_traits>
#include <utility>
#include <vector>

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC push_options
#pragma GCC optimize("O3")
#endif

template <class S, auto op, auto e, class F, auto mapping, auto composition, auto id, bool commutative = false>
class LazyReversibleTreap {
	struct Empty {};
	using Back = std::conditional_t<commutative, Empty, S>;
	struct Node {
		int left = 0, right = 0;
		std::uint32_t count : 30 = 1;
		std::uint32_t pending : 1 = 0;
		std::uint32_t reversed : 1 = 0;
		std::uint32_t priority;
		S value, product;
		[[no_unique_address]] Back back;
		F lazy = id();
		static Back make_back(const S &value) {
			if constexpr (commutative) return {};
			else return value;
		}
		Node(S value, std::uint32_t priority) : priority(priority), value(std::move(value)), product(this->value), back(make_back(this->value)) {}
	};
	std::vector<Node> t;
	SplitMix64 rng;
	int root = 0, free = 0;
	bool lazy_applied = false;
	int count(int x) const { return t[x].count; }
	template <bool resize = true>
	void pull(int x) {
		auto &v = t[x];
		int l = v.left, r = v.right;
		if constexpr (resize) v.count = count(l) + count(r) + 1;
		v.product = l ? op(t[l].product, v.value) : v.value;
		if (r) v.product = op(std::move(v.product), t[r].product);
		if constexpr (!commutative) {
			v.back = r ? op(t[r].back, v.value) : v.value;
			if (l) v.back = op(std::move(v.back), t[l].back);
		}
	}
	void flip(int x) {
		if (!x || count(x) == 1) return;
		auto &v = t[x];
		std::swap(v.left, v.right);
		if constexpr (!commutative) std::swap(v.product, v.back);
		v.reversed ^= 1;
	}
	void act(int x, const F &f) {
		if (!x) return;
		auto &v = t[x];
		if (count(x) == 1) {
			v.value = v.product = mapping(f, v.product, 1);
			if constexpr (!commutative) v.back = v.product;
			return;
		}
		v.product = mapping(f, v.product, count(x));
		if constexpr (!commutative) v.back = mapping(f, v.back, count(x));
		v.lazy = v.pending ? composition(f, v.lazy) : f;
		v.pending = true;
	}
	void push(int x) {
		auto &v = t[x];
		if (v.reversed) {
			flip(v.left);
			flip(v.right);
			v.reversed = 0;
		}
		if (v.pending) {
			v.value = mapping(v.lazy, v.value, 1);
			act(v.left, v.lazy);
			act(v.right, v.lazy);
			v.pending = false;
		}
	}
	int make(S value) {
		if (free) {
			int x = free;
			free = t[x].left;
			t[x] = Node(std::move(value), std::uint32_t(rng()));
			return x;
		}
		assert(t.size() <= (std::size_t(1) << 30) - 1);
		t.emplace_back(std::move(value), std::uint32_t(rng()));
		return int(t.size()) - 1;
	}
	std::pair<int, int> split(int x, int k) {
		if (!x) return {0, 0};
		if (!k) return {0, x};
		if (k == count(x)) return {x, 0};
		push(x);
		int left = count(t[x].left);
		if (k <= left) {
			auto [a, b] = split(t[x].left, k);
			t[x].left = b;
			pull(x);
			return {a, x};
		}
		auto [a, b] = split(t[x].right, k - left - 1);
		t[x].right = a;
		pull(x);
		return {x, b};
	}
	int merge(int a, int b) {
		if (!a || !b) return a | b;
		if (t[a].priority > t[b].priority) {
			push(a);
			t[a].right = merge(t[a].right, b);
			pull(a);
			return a;
		}
		push(b);
		t[b].left = merge(a, t[b].left);
		pull(b);
		return b;
	}
	int insert_node(int x, int p, int added) {
		if (!x) return added;
		if (t[added].priority >= t[x].priority) {
			auto [a, b] = split(x, p);
			t[added].left = a;
			t[added].right = b;
			pull(added);
			return added;
		}
		push(x);
		int left = count(t[x].left);
		if (p <= left) t[x].left = insert_node(t[x].left, p, added);
		else t[x].right = insert_node(t[x].right, p - left - 1, added);
		pull(x);
		return x;
	}
	int erase_node(int x, int p, S &value) {
		push(x);
		int left = count(t[x].left);
		if (p == left) {
			value = std::move(t[x].value);
			int result = merge(t[x].left, t[x].right);
			t[x].left = free;
			free = x;
			return result;
		}
		if (p < left) t[x].left = erase_node(t[x].left, p, value);
		else t[x].right = erase_node(t[x].right, p - left - 1, value);
		pull(x);
		return x;
	}
	void set_node(int x, int p, S value) {
		push(x);
		int left = count(t[x].left);
		if (p == left) t[x].value = std::move(value);
		else if (p < left) set_node(t[x].left, p, std::move(value));
		else set_node(t[x].right, p - left - 1, std::move(value));
		pull<false>(x);
	}
	S fold(int x, int l, int r, bool reversed = false) const {
		for (;;) {
			const auto &v = t[x];
			if (!l && r == count(x)) {
				if constexpr (!commutative) if (reversed) return v.back;
				return v.product;
			}
			int a = reversed ? v.right : v.left, b = reversed ? v.left : v.right;
			int left = count(a);
			reversed ^= v.reversed;
			if (r <= left) { x = a; continue; }
			if (left < l) { x = b; l -= left + 1; r -= left + 1; continue; }
			S result = v.value;
			if (l < left) result = op(fold(a, l, left, reversed), std::move(result));
			if (left + 1 < r) result = op(std::move(result), fold(b, 0, r - left - 1, reversed));
			return result;
		}
	}
	S fold_lazy(int x, int l, int r, const F *carry = nullptr, bool reversed = false) const {
		const auto &v = t[x];
		if (!l && r == count(x)) {
			S result = v.product;
			if constexpr (!commutative) if (reversed) result = v.back;
			return carry ? mapping(*carry, std::move(result), count(x)) : result;
		}
		F combined = id();
		if (v.pending) {
			combined = carry ? composition(*carry, v.lazy) : v.lazy;
			carry = &combined;
		}
		int a = reversed ? v.right : v.left, b = reversed ? v.left : v.right;
		int left = count(a);
		reversed ^= v.reversed;
		if (r <= left) return fold_lazy(a, l, r, carry, reversed);
		if (left < l) return fold_lazy(b, l - left - 1, r - left - 1, carry, reversed);
		S result = carry ? mapping(*carry, v.value, 1) : v.value;
		if (l < left) result = op(fold_lazy(a, l, left, carry, reversed), std::move(result));
		if (left + 1 < r) result = op(std::move(result), fold_lazy(b, 0, r - left - 1, carry, reversed));
		return result;
	}
	void apply_node(int x, int l, int r, const F &f) {
		if (!l && r == count(x)) { act(x, f); return; }
		push(x);
		int left = count(t[x].left);
		if (l < left) apply_node(t[x].left, l, std::min(r, left), f);
		if (l <= left && left < r) t[x].value = mapping(f, t[x].value, 1);
		if (left + 1 < r) apply_node(t[x].right, std::max(l - left - 1, 0), r - left - 1, f);
		pull<false>(x);
	}
	int reverse_node(int x, int l, int r) {
		if (!l && r == count(x)) { flip(x); return x; }
		push(x);
		int left = count(t[x].left);
		if (r <= left) t[x].left = reverse_node(t[x].left, l, r);
		else if (left < l) t[x].right = reverse_node(t[x].right, l - left - 1, r - left - 1);
		else {
			auto [a, b] = split(t[x].left, l);
			auto [c, d] = split(t[x].right, r - left - 1);
			flip(b);
			flip(c);
			t[x].left = merge(a, c);
			t[x].right = merge(b, d);
		}
		if constexpr (!commutative) pull<false>(x);
		return x;
	}
	void collect(int x, std::vector<S> &values) {
		if (!x) return;
		push(x);
		collect(t[x].left, values);
		values.push_back(t[x].value);
		collect(t[x].right, values);
	}
	void bounds(int l, int r) const { assert(0 <= l && l <= r && r <= size()); (void)l; (void)r; }

  public:
	using value_type = S;
	using action_type = F;
	explicit LazyReversibleTreap(std::uint64_t seed = 0) : rng(seed) { t.emplace_back(e(), 0); t[0].count = 0; }
	explicit LazyReversibleTreap(const std::vector<S> &values, std::uint64_t seed = 0) : LazyReversibleTreap(seed) { assign(values); }
	LazyReversibleTreap(const LazyReversibleTreap &) = default;
	LazyReversibleTreap &operator=(const LazyReversibleTreap &) = default;
	LazyReversibleTreap(LazyReversibleTreap &&other) : LazyReversibleTreap() { swap(other); }
	LazyReversibleTreap &operator=(LazyReversibleTreap &&other) {
		if (this != &other) { LazyReversibleTreap moved(std::move(other)); swap(moved); }
		return *this;
	}
	void swap(LazyReversibleTreap &other) noexcept {
		t.swap(other.t);
		std::swap(rng, other.rng);
		std::swap(root, other.root);
		std::swap(free, other.free);
		std::swap(lazy_applied, other.lazy_applied);
	}
	int size() const { return count(root); }
	bool empty() const { return !root; }
	void reserve(std::size_t n) { assert(n < (std::size_t(1) << 30)); t.reserve(n + 1); }
	std::size_t memory_usage() const { return t.capacity() * sizeof(Node); }
	void clear() { t.erase(t.begin() + 1, t.end()); root = free = 0; lazy_applied = false; }
	void assign(const std::vector<S> &values) {
		clear();
		reserve(values.size());
		std::vector<int> path;
		for (const S &value : values) {
			int x = make(value), last = 0;
			while (!path.empty() && t[path.back()].priority <= t[x].priority) {
				last = path.back(); path.pop_back(); pull(last);
			}
			t[x].left = last;
			if (!path.empty()) t[path.back()].right = x;
			path.push_back(x);
		}
		if (!path.empty()) root = path[0];
		while (!path.empty()) { pull(path.back()); path.pop_back(); }
	}
	void insert(int p, S value) { bounds(p, p); root = insert_node(root, p, make(std::move(value))); }
	S erase(int p) { bounds(p, p + 1); S value = e(); root = erase_node(root, p, value); return value; }
	S get(int p) {
		bounds(p, p + 1);
		int x = root;
		for (;;) {
			push(x);
			int left = count(t[x].left);
			if (p == left) return t[x].value;
			if (p < left) x = t[x].left;
			else p -= left + 1, x = t[x].right;
		}
	}
	void set(int p, S value) { bounds(p, p + 1); set_node(root, p, std::move(value)); }
	S prod(int l, int r) { bounds(l, r); return l == r ? e() : lazy_applied ? fold_lazy(root, l, r) : fold(root, l, r); }
	S all_prod() const { return t[root].product; }
	void apply(int p, const F &f) { apply(p, p + 1, f); }
	void apply(int l, int r, const F &f) { bounds(l, r); if (l != r) { lazy_applied = true; apply_node(root, l, r, f); } }
	void reverse(int l, int r) { bounds(l, r); if (r - l > 1) root = reverse_node(root, l, r); }
	void rotate(int l, int m, int r) {
		bounds(l, m); bounds(m, r);
		if (l == m || m == r) return;
		auto [a, b] = split(root, l);
		auto [c, d] = split(b, m - l);
		auto [f, g] = split(d, r - m);
		root = merge(a, merge(f, merge(c, g)));
	}
	void move(int l, int r, int p) {
		bounds(l, r);
		assert(0 <= p && p <= size() - (r - l));
		if (l == r || l == p) return;
		auto [a, b] = split(root, l);
		auto [c, d] = split(b, r - l);
		auto [f, g] = split(merge(a, d), p);
		root = merge(f, merge(c, g));
	}
	std::vector<S> to_vector() { std::vector<S> values; values.reserve(size()); collect(root, values); return values; }
};

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC pop_options
#endif