test/ALPC-L.test.cpp

• View this file on GitHub
• Last update: 2023-03-10 16:51:37+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/practice2/submissions/39569424

Depends on

• lazySegmentTree (区間更新・区間和セグ木) (src/dataStructure/lazySegmentTree.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

// struct vData {
// 	long long zero, one, inv;
// 	constexpr vData(long long _zero = 0LL, long long _one = 0LL, long long _inv = 0LL) : zero(_zero), one(_one), inv(_inv) {}
// };
// 
// struct vM {
// 	using valueType = vData;
// 	static constexpr vData identity{};
// 	static vData operation(const vData& a, const vData& b) {
// 		return vData{
// 			a.zero + b.zero, 
// 			a.one + b.one,
// 			a.inv + b.inv + a.one * b.zero
// 		};
// 	}
// };
// 
// struct oM {
// 	using valueType = bool;
// 	static constexpr bool identity{};
// 	static bool operation(const bool& a, const bool& b) {
// 		return (a and !b) or (!a and b);
// 	}
// };
// 
// struct action {
// 	using valueMonoid = vM;
// 	using operatorMonoid = oM;
// 	static vData mapping(const vData& a, const bool& b) {
// 		if (!b) {
// 			return a;
// 		}
// 		else {
// 			return vData{
// 				a.one,
// 				a.zero,
// 				a.one * a.zero - a.inv
// 			};
// 		}
// 	}
// };

#include "../src/dataStructure/lazySegmentTree.hpp"

#include <iostream>
#include <vector>

int main() {
	// std::cin.tie(nullptr);
	// std::ios::sync_with_stdio(false);
	// int n, q; std::cin >> n >> q;
	// std::vector<vData> A(n);
	// for (int i = 0 ; i < n ; i++) {
	// 	int x; std::cin >> x;
	// 	if (x == 0) {
	// 		A[i] = vData{ 1, 0, 0 };
	// 	}
	// 	else {
	// 		A[i] = vData{ 0, 1, 0 };
	// 	}
	// }
	// zawa::lazySegmentTree<action> S(A);
	// for (int _ = 0 ; _ < q ; _++) {
	// 	int t, l, r; std::cin >> t >> l >> r;
	// 	l--;
	// 	if (t == 1) {
	// 		S.update(l, r, true);
	// 	}
	// 	else {
	// 		std::cout << S.prod(l, r).inv << std::endl;
	// 	}
	// }

	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Library Practice Contest - L Lazy Segment Tree
 * https://atcoder.jp/contests/practice2/submissions/39569424
 */

#line 1 "test/ALPC-L.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

// struct vData {
// 	long long zero, one, inv;
// 	constexpr vData(long long _zero = 0LL, long long _one = 0LL, long long _inv = 0LL) : zero(_zero), one(_one), inv(_inv) {}
// };
// 
// struct vM {
// 	using valueType = vData;
// 	static constexpr vData identity{};
// 	static vData operation(const vData& a, const vData& b) {
// 		return vData{
// 			a.zero + b.zero, 
// 			a.one + b.one,
// 			a.inv + b.inv + a.one * b.zero
// 		};
// 	}
// };
// 
// struct oM {
// 	using valueType = bool;
// 	static constexpr bool identity{};
// 	static bool operation(const bool& a, const bool& b) {
// 		return (a and !b) or (!a and b);
// 	}
// };
// 
// struct action {
// 	using valueMonoid = vM;
// 	using operatorMonoid = oM;
// 	static vData mapping(const vData& a, const bool& b) {
// 		if (!b) {
// 			return a;
// 		}
// 		else {
// 			return vData{
// 				a.one,
// 				a.zero,
// 				a.one * a.zero - a.inv
// 			};
// 		}
// 	}
// };

#line 2 "src/dataStructure/lazySegmentTree.hpp"

#include <vector>
#include <cassert>

namespace zawa {

template <class structure>
class lazySegmentTree {
	// valueMonoid prodの時の演算
	using V = typename structure::valueMonoid::valueType;
	// operatorMonoid updateの時の演算
	using O = typename structure::operatorMonoid::valueType;
private:
	// prodの単位元
	static constexpr V vId = structure::valueMonoid::identity;
	// updateの単位元
	static constexpr O oId = structure::operatorMonoid::identity;

	struct node {
		V value;
		O lazy;
		node() : value(vId), lazy(oId) {}
	};

	// @brief ノードvの左子の添字を返す
	constexpr std::size_t left(std::size_t v) const {
		return v << 1;
	}
	// @brief ノードvの右子の添字を返す
	constexpr std::size_t right(std::size_t v) const {
		return v << 1 | 1;
	}
	// @brief ノードvの親の添字を返す。
	constexpr std::size_t parent(std::size_t v) const {
		return (v >> 1);
	}

	std::size_t N;
	std::size_t powTwo;
	std::vector<node> dat;

	// @brief 遅延した値を子に伝播する
	void propagate(std::size_t v) {
		if (dat[v].lazy == oId) {
			return;
		}
		dat[v].value = structure::mapping(dat[v].value, dat[v].lazy);
		if (right(v) < dat.size()) {
			dat[left(v)].lazy = structure::operatorMonoid::operation(dat[left(v)].lazy, dat[v].lazy);
			dat[right(v)].lazy = structure::operatorMonoid::operation(dat[right(v)].lazy, dat[v].lazy);
		}
		dat[v].lazy = oId;
	}

	// @brief 内部更新用
	// LRがクエリの範囲、lrがvの持つ範囲
	void update(std::size_t L, std::size_t R, std::size_t l, std::size_t r, std::size_t v, const O& value) {
		// 先延ばししていたものを評価する
		propagate(v);

		// まったくかぶってない時、特に何もしない
		if (R <= l or r <= L) {
			return;
		}

		// lrがLRにまたがっている時、先延ばしにする
		if (L <= l and r <= R) {
			dat[v].lazy = structure::operatorMonoid::operation(dat[v].lazy, value);
			propagate(v);
		}
		// 子を計算する場合
		else {
			assert(right(v) < dat.size());
			std::size_t childRange = (r - l) >> 1;
			update(L, R, l, l + childRange, left(v), value);
			update(L, R, l + childRange, r, right(v), value);
			dat[v].value = structure::valueMonoid::operation(dat[left(v)].value, dat[right(v)].value);
		}
	}

	// @brief 内部計算用
	// LRがクエリの範囲、lrがvの持つ範囲
	V prod(std::size_t L, std::size_t R, std::size_t l, std::size_t r, std::size_t v) {

		// 区間が被ってない時、単位元を返す
		if (R <= l or r <= L) {
			return vId;
		}

		// 先延ばしが許されなくなったので遅延評価する
		propagate(v);

		// lrがLRにすっぽりおさまっている時、そのノードの値を掛け合わせる
		if (L <= l and r <= R) {
			return dat[v].value;
		}
		// 子を辿る
		else {
			V res = vId;
			std::size_t childRange = (r - l) >> 1;
			assert(right(v) < dat.size());
			res = structure::valueMonoid::operation(res, prod(L, R, l, l + childRange, left(v)));
			res = structure::valueMonoid::operation(res, prod(L, R, l + childRange, r, right(v)));
			return res;
		}
	}

public:
	// @brief A = ( vId, vId, ... , vId ), |A| = Nとする
	// @param N |A|
	lazySegmentTree(std::size_t _N) : N(_N) {
		std::size_t sz = 1;
		while (sz < N) {
			sz <<= 1;
		}
		powTwo = sz;
		dat.resize((sz << 1));
	}

	// @brief Aを引数の列で初期化する
	// @param A 扱う列
	lazySegmentTree(const std::vector<V>& A) : N(A.size()) {
		std::size_t sz = 1;
		while (sz < N) {
			sz <<= 1;
		}
		powTwo = sz;
		dat.resize((sz << 1));
		for (std::size_t i = 0 ; i < A.size() ; i++) {
			dat[i + powTwo].value = A[i];
		}
		for (std::size_t i = powTwo - 1 ; i > 0 ; i--) {
			dat[i].value = structure::valueMonoid::operation(dat[left(i)].value, dat[right(i)].value);
		}
	}	
	
	// @brief A_l .. A_{r - 1}にvalueで列を更新する
	// @param L 左
	// @param R 右、半開区間で与える必要がある
	// @param value 更新させる値
	void update(std::size_t L, std::size_t R, const O& value) {
		assert(0 <= L and R <= N);
		assert(L < R);
		update(L, R, 0, powTwo, 1, value);
	}

	// @brief A_l .. A_R の総積(総valueMonoid::operation)を得る
	// @param L 左
	// @param R 右、半開区間で与える必要がある
	// @return 計算結果
	V prod(std::size_t L, std::size_t R) {
		assert(0 <= L and R <= N);
		if (L == R) {
			return vId;
		}
		return prod(L, R, 0, powTwo, 1);
	}

	// @brief デバッグ用、datを返す
	// @return dat
	inline std::vector<node> _dat() const {
		return dat;
	}
};

} // namespace zawa
#line 46 "test/ALPC-L.test.cpp"

#include <iostream>
#line 49 "test/ALPC-L.test.cpp"

int main() {
	// std::cin.tie(nullptr);
	// std::ios::sync_with_stdio(false);
	// int n, q; std::cin >> n >> q;
	// std::vector<vData> A(n);
	// for (int i = 0 ; i < n ; i++) {
	// 	int x; std::cin >> x;
	// 	if (x == 0) {
	// 		A[i] = vData{ 1, 0, 0 };
	// 	}
	// 	else {
	// 		A[i] = vData{ 0, 1, 0 };
	// 	}
	// }
	// zawa::lazySegmentTree<action> S(A);
	// for (int _ = 0 ; _ < q ; _++) {
	// 	int t, l, r; std::cin >> t >> l >> r;
	// 	l--;
	// 	if (t == 1) {
	// 		S.update(l, r, true);
	// 	}
	// 	else {
	// 		std::cout << S.prod(l, r).inv << std::endl;
	// 	}
	// }

	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Library Practice Contest - L Lazy Segment Tree
 * https://atcoder.jp/contests/practice2/submissions/39569424
 */

Back to top page