tkmst201's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub tkmst201/Library

:heavy_check_mark: Test/DynamicSegmentTree.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"

#include "DataStructure/DynamicSegmentTree.hpp"
#include "Mathematics/ModInt.hpp"

#include <cstdio>

int main() {
	int N, Q;
	scanf("%d %d", &N, &Q);
	
	using mint = ModInt<998244353>;
	using pmm = std::pair<mint, mint>;
	
	DynamicSegmentTree<pmm> seg(N, pmm(1, 0), [](const pmm & a, const pmm & b) -> pmm {
		return {a.first * b.first, b.first * a.second + b.second};
	});
	
	for (int i = 0; i < N; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		seg.set(i, {a, b});
	}
	
	while (Q--) {
		int q, a, b, c;
		scanf("%d %d %d %d", &q, &a, &b, &c);
		if (q == 0) {
			seg.set(a, {b, c});
		}
		else {
			pmm v = seg.fold(a, b);
			mint ans = v.first * c + v.second;
			printf("%d\n", ans.val());
		}
	}
}
#line 1 "Test/DynamicSegmentTree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"

#line 1 "DataStructure/DynamicSegmentTree.hpp"



#include <functional>
#include <cassert>
#include <stack>
#include <cstdint>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/DynamicSegmentTree.hpp
 */
template<typename T>
struct DynamicSegmentTree {
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;
	using F = std::function<value_type (const_reference, const_reference)>;
	
private:
	struct Node;
	using node_ptr = Node *;
	using const_ptr = const Node * const;
	struct Node {
		value_type val;
		node_ptr child[2] {nullptr, nullptr};
		Node() = default;
		Node(const_reference val) : val(val) {}
	};
	
	template<typename U>
	struct Data {
		U node;
		size_type l, r;
		Data(U node, size_type l, size_type r) : node(node), l(l), r(r) {}
	};
	
private:
	size_type n, n_;
	int log_n;
	value_type id_elem;
	F f;
	node_ptr root = nullptr;
	
public:
	DynamicSegmentTree(size_type n, const_reference id_elem, const F & f)
		: n(n), id_elem(id_elem), f(f), root(nullptr) {
		n_ = 1;
		log_n = 0;
		while (n_ < n) n_ <<= 1, ++log_n;
	}
	
	DynamicSegmentTree(const DynamicSegmentTree & rhs) {
		*this = rhs;
	}
	
	DynamicSegmentTree(DynamicSegmentTree && rhs) {
		*this = std::forward<DynamicSegmentTree>(rhs);
	}
	
	~DynamicSegmentTree() {
		clear();
	}
	
	DynamicSegmentTree & operator =(const DynamicSegmentTree & rhs) {
		if (this != &rhs) {
			clear();
			n = rhs.n;
			n_ = rhs.n_;
			log_n = rhs.log_n;
			id_elem = rhs.id_elem;
			f = rhs.f;
			root = copy_dfs(rhs.root, nullptr);
		}
		return *this;
	}
	
	DynamicSegmentTree & operator =(DynamicSegmentTree && rhs) {
		if (this != &rhs) {
			clear();
			n = rhs.n;
			n_ = rhs.n_;
			log_n = rhs.log_n;
			id_elem = rhs.id_elem;
			f = rhs.f;
			root = rhs.root;
			rhs.root = nullptr;
		}
		return *this;
	}
	
	void clear() {
		clear_subtree(root);
		root = nullptr;
	}
	
	void clear(size_type l, size_type r) {
		assert(l <= r);
		assert(r <= size());
		if ((l == 0 && r == n_) || n_ == 1) { clear(); return; }
		if (l == r || !root) return;
		std::stack<Data<node_ptr>> stk;
		stk.emplace(root, 0, n_);
		while (!stk.empty()) {
			auto [node, cl, cr] = stk.top();
			stk.pop();
			if (cl == cr) {
				node->val = f(node->child[0] ? node->child[0]->val : id_elem, node->child[1] ? node->child[1]->val : id_elem);
				continue;
			}
			const size_type m = cl + ((cr - cl) >> 1);
			stk.emplace(node, 0, 0);
			if (m < r && node->child[1]) {
				if (l <= m && cr <= r) {
					clear_subtree(node->child[1]);
					node->child[1] = nullptr;
				}
				else stk.emplace(node->child[1], m, cr);
			}
			if (l < m && node->child[0]) {
				if (l <= cl && m <= r) {
					clear_subtree(node->child[0]);
					node->child[0] = nullptr;
				}
				else stk.emplace(node->child[0], cl, m);
			}
		}
	}
	
	size_type size() const noexcept {
		return n;
	}
	
	void set(size_type k, const_reference x) {
		assert(k < size());
		if (!root) root = new Node;
		node_ptr node = root;
		std::stack<node_ptr> stk;
		for (int i = log_n - 1; i >= 0; --i) {
			stk.emplace(node);
			const bool r = k >> i & 1;
			if (!node->child[r]) node->child[r] = new Node;
			node = node->child[r];
		}
		node->val = x;
		while (!stk.empty()) {
			node = stk.top();
			stk.pop();
			node->val = f(node->child[0] ? node->child[0]->val : id_elem, node->child[1] ? node->child[1]->val : id_elem);
		}
	}
	
	value_type get(size_type k) const noexcept {
		assert(k < size());
		if (!root) return id_elem;
		node_ptr node = root;
		for (int i = log_n - 1; i >= 0; --i) {
			const bool r = k >> i & 1;
			if (!node->child[r]) return id_elem;
			node = node->child[r];
		}
		return node->val;
	}
	
	value_type fold(size_type l, size_type r) const noexcept {
		assert(l <= r);
		assert(r <= size());
		if (l == r || !root) return id_elem;
		value_type res = id_elem;
		std::stack<Data<node_ptr>> stk;
		stk.emplace(root, 0, n_);
		while (!stk.empty()) {
			auto [node, cl, cr] = stk.top();
			stk.pop();
			if (l <= cl && cr <= r) res = f(res, node->val);
			else {
				const size_type m = cl + ((cr - cl) >> 1);
				if (m < r && node->child[1]) stk.emplace(node->child[1], m, cr);
				if (l < m && node->child[0]) stk.emplace(node->child[0], cl, m);
			}
		}
		return res;
	}
	
	value_type fold_all() const noexcept {
		if (!root) return id_elem;
		return root->val;
	}
	
	void swap(DynamicSegmentTree & rhs, size_type l, size_type r) {
		assert(size() == rhs.size());
		assert(id_elem == rhs.id_elem);
		assert(l <= r);
		assert(r <= size());
		if (this == &rhs) return;
		if (l == r) return;
		if ((l == 0 && r == n_) || n_ == 1) { std::swap(root, rhs.root); return; }
		if (!root && !rhs.root) return;
		if (!root) root = new Node{id_elem};
		if (!rhs.root) rhs.root = new Node{id_elem};
		std::stack<Data<std::pair<node_ptr, node_ptr>>> stk;
		stk.emplace(std::make_pair(root, rhs.root), 0, n_);
		while (!stk.empty()) {
			auto [nodes, cl, cr] = stk.top();
			auto [node1, node2] = nodes;
			stk.pop();
			if (cl == cr) {
				node1->val = f(node1->child[0] ? node1->child[0]->val : id_elem, node1->child[1] ? node1->child[1]->val : id_elem);
				node2->val = f(node2->child[0] ? node2->child[0]->val : id_elem, node2->child[1] ? node2->child[1]->val : id_elem);
				continue;
			}
			const size_type m = cl + ((cr - cl) >> 1);
			stk.emplace(nodes, 0, 0);
			if (m < r && (node1->child[1] || node2->child[1])) {
				if (l <= m && cr <= r) std::swap(node1->child[1], node2->child[1]);
				else {
					if (!node1->child[1]) node1->child[1] = new Node;
					else if (!node2->child[1]) node2->child[1] = new Node;
					stk.emplace(std::make_pair(node1->child[1], node2->child[1]), m, cr);
				}
			}
			if (l < m && (node1->child[0] || node2->child[0])) {
				if (l <= cl && m <= r) std::swap(node1->child[0], node2->child[0]);
				else {
					if (!node1->child[0]) node1->child[0] = new Node;
					else if (!node2->child[0]) node2->child[0] = new Node;
					stk.emplace(std::make_pair(node1->child[0], node2->child[0]), cl, m);
				}
			}
		}
	}
	
private:
	node_ptr copy_dfs(const_ptr q, node_ptr r) {
		if (!q) return nullptr;
		node_ptr res = new Node{q->val};
		res->child[0] = copy_dfs(q->child[0], res);
		res->child[1] = copy_dfs(q->child[1], res);
		return res;
	}
	
	void clear_subtree(node_ptr r) {
		if (!r) return;
		std::stack<node_ptr> stk;
		stk.emplace(r);
		while (!stk.empty()) {
			node_ptr node = stk.top();
			stk.pop();
			if (node->child[0]) stk.emplace(node->child[0]);
			if (node->child[1]) stk.emplace(node->child[1]);
			delete node;
		}
	}
};


#line 1 "Mathematics/ModInt.hpp"



#line 5 "Mathematics/ModInt.hpp"
#include <iostream>
#line 7 "Mathematics/ModInt.hpp"

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/ModInt.hpp
 */
template<int M>
struct ModInt {
	static_assert(M > 0);
	
	using value_type = int;
	using calc_type = std::int_fast64_t;
	
private:
	value_type val_;
	
public:
	constexpr ModInt(calc_type val = 0) : val_(val % M + (val >= 0 ? 0 : M)) {}
	constexpr value_type val() const noexcept { return val_; }
	constexpr static decltype(M) mod() noexcept { return M; }
	
	explicit constexpr operator bool() const noexcept { return val_; }
	constexpr bool operator !() const noexcept { return !static_cast<bool>(*this); }
	constexpr ModInt operator +() const noexcept { return *this; }
	constexpr ModInt operator -() const noexcept { return ModInt(val_ == 0 ? 0 : M - val_); }
	constexpr ModInt operator ++(int) noexcept { ModInt res = *this; ++*this; return res; }
	constexpr ModInt operator --(int) noexcept { ModInt res = *this; --*this; return res; }
	constexpr ModInt & operator ++() noexcept { val_ = val_ + 1 == M ? 0 : val_ + 1; return *this; }
	constexpr ModInt & operator --() noexcept { val_ = val_ == 0 ? M - 1 : val_ - 1; return *this; }
	constexpr ModInt & operator +=(const ModInt & rhs) noexcept { val_ += val_ < M - rhs.val_ ? rhs.val_ : rhs.val_ - M; return *this; }
	constexpr ModInt & operator -=(const ModInt & rhs) noexcept { val_ += val_ >= rhs.val_ ? -rhs.val_ : M - rhs.val_; return *this; }
	constexpr ModInt & operator *=(const ModInt & rhs) noexcept { val_ = static_cast<calc_type>(val_) * rhs.val_ % M; return *this; }
	constexpr ModInt & operator /=(const ModInt & rhs) noexcept { return *this *= rhs.inv(); }
	friend constexpr ModInt operator +(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) += rhs; }
	friend constexpr ModInt operator -(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) -= rhs; }
	friend constexpr ModInt operator *(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) *= rhs; }
	friend constexpr ModInt operator /(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) /= rhs; }
	friend constexpr bool operator ==(const ModInt & lhs, const ModInt & rhs) noexcept { return lhs.val_ == rhs.val_; }
	friend constexpr bool operator !=(const ModInt & lhs, const ModInt & rhs) noexcept { return !(lhs == rhs); }
	friend std::ostream & operator <<(std::ostream & os, const ModInt & rhs) { return os << rhs.val_; }
	friend std::istream & operator >>(std::istream & is, ModInt & rhs) { calc_type x; is >> x; rhs = ModInt(x); return is; }
	
	constexpr ModInt pow(calc_type n) const noexcept {
		ModInt res = 1, x = val_;
		if (n < 0) { x = x.inv(); n = -n; }
		while (n) { if (n & 1) res *= x; x *= x; n >>= 1; }
		return res;
	}
	
	constexpr ModInt inv() const noexcept {
		value_type a = val_, a1 = 1, b = M, b1 = 0;
		while (b > 0) {
			const value_type q = a / b;
			value_type tmp = a - q * b; a = b; b = tmp;
			tmp = a1 - q * b1; a1 = b1; b1 = tmp;
		}
		assert(a == 1);
		if (a1 < 0) a1 += M;
		return a1;
	}
};


#line 5 "Test/DynamicSegmentTree.test.cpp"

#include <cstdio>

int main() {
	int N, Q;
	scanf("%d %d", &N, &Q);
	
	using mint = ModInt<998244353>;
	using pmm = std::pair<mint, mint>;
	
	DynamicSegmentTree<pmm> seg(N, pmm(1, 0), [](const pmm & a, const pmm & b) -> pmm {
		return {a.first * b.first, b.first * a.second + b.second};
	});
	
	for (int i = 0; i < N; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		seg.set(i, {a, b});
	}
	
	while (Q--) {
		int q, a, b, c;
		scanf("%d %d %d %d", &q, &a, &b, &c);
		if (q == 0) {
			seg.set(a, {b, c});
		}
		else {
			pmm v = seg.fold(a, b);
			mint ans = v.first * c + v.second;
			printf("%d\n", ans.val());
		}
	}
}
Back to top page