zawatins-library

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

View the Project on GitHub zawa-tin/zawatins-library

:heavy_check_mark: test/lazySquareDecomp-AOJ-RAQRSQ.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G"

#include "../src/dataStructure/lazySquareDecomp.hpp"
#include "../src/utility/monoid/rangeAddMonoid.hpp"
#include "../src/utility/monoid/addMonoid.hpp"

struct addAction {
	using valueMonoid = zawa::rangeAddMonoid<long long>;
	using operatorMonoid = zawa::addMonoid<long long>;
	static valueMonoid::valueType mapping(const valueMonoid::valueType& a, const operatorMonoid::valueType& b) {
		return valueMonoid::valueType(a.value + a.size * b, a.size);
	}
};

#include <iostream>
#include <vector>

int main() {
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	int N, Q; std::cin >> N >> Q;
	zawa::lazySquareDecomp<addAction> sq(std::vector(N, addAction::valueMonoid::valueType(0LL, 1ULL)));
	for (int _ = 0 ; _ < Q ; _++) {
		int type; std::cin >> type;
		if (type == 0) {
			int s, t, x; std::cin >> s >> t >> x;
			sq.update(s - 1, t, x);
		}
		if (type == 1) {
			int s, t; std::cin >> s >> t;
			std::cout << sq.prod(s - 1, t).value << std::endl;
		}
	}
}
#line 1 "test/lazySquareDecomp-AOJ-RAQRSQ.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G"

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

#include <vector>
#include <cmath>
#include <algorithm>

namespace zawa {

template <class structure>
class lazySquareDecomp {
	using V = typename structure::valueMonoid::valueType;
	using O = typename structure::operatorMonoid::valueType;

private:
	static constexpr V vId = structure::valueMonoid::identity;
	static constexpr O oId = structure::operatorMonoid::identity;
	struct node {
		V value;
		O lazy;
		node() : value(vId), lazy(oId) {}
	};
	int square;
	std::vector<V> dat;
	std::vector<node> bucket;

	void propagate(int pos) {
		int l = square * pos;
		for (int i = 0 ; i < square ; i++) {
			dat[l + i] = structure::mapping(dat[l + i], bucket[pos].lazy);	
		}
		bucket[pos].lazy = oId;
	}

	void update(int pos) {
		bucket[pos].value = vId;
		int l = square * pos;
		for (int i = 0 ; i < square and l + i < (int)dat.size() ; i++) {
			bucket[pos].value = structure::valueMonoid::operation(bucket[pos].value, dat[l + i]);
		}
	}
	
public:
	lazySquareDecomp(int n) : square(std::sqrt(n + 1)), dat(n, vId), bucket((n + square - 1) / square) {
		for (std::size_t i = 0 ; i < dat.size() ; i++) {
			bucket[i / square].value = structure::valueMonoid::operation(bucket[i / square].value, dat[i]);
		}
	}
	lazySquareDecomp(const std::vector<V>& A) : square(std::sqrt(A.size() + 1)), dat(A), bucket((A.size() + square - 1) / square) {
		for (std::size_t i = 0 ; i < dat.size() ; i++) {
			bucket[i / square].value = structure::valueMonoid::operation(bucket[i / square].value, dat[i]);
		}
	}

	void update(int pos, const O& value) {
		if (bucket[pos / square].lazy != oId) {
			propagate(pos / square);
		}
		dat[pos] = structure::mapping(dat[pos], value);
		update(pos / square);
	}	

	void update(int l, int r, const O& value) {	
		for (int i = 0 ; i < (int)bucket.size() ; i++) {
			int p = i * square, q = (i + 1) * square;
			if (r <= p or q <= l) {
				continue;
			}
			if (l <= p and q <= r) {
				bucket[i].lazy = structure::operatorMonoid::operation(bucket[i].lazy, value);
			}
			else {
				if (bucket[i].lazy != oId) {
					propagate(i);
				}
				for (int j = std::max(l, p) ; j < std::min({ q, r, (int)dat.size() }) ; j++) {
					dat[j] = structure::mapping(dat[j], value);
				}
				update(i);
			}
		}
	}

	V prod(int l, int r) {
		V res = vId;
		for (int i = 0 ; i < (int)bucket.size() ; i++) {
			int p = i * square, q = (i + 1) * square;
			if (r <= p or q <= l) {
				continue;
			}
			if (l <= p and q <= r) {
				if (bucket[i].lazy != oId) {
					res = structure::valueMonoid::operation(res, structure::mapping(bucket[i].value, bucket[i].lazy));
				}
				else {
					res = structure::valueMonoid::operation(res, bucket[i].value);
				}
			}
			else {
				if (bucket[i].lazy != oId) {
					propagate(i);
					update(i);
				}
				for (int j = std::max(l, p) ; j < std::min({ q, r, (int)dat.size() }) ; j++) {
					res = structure::valueMonoid::operation(res, dat[j]);
				}
			}
		}
		return res;
	}
};

} // namespace zawa
#line 2 "src/utility/monoid/rangeAddMonoid.hpp"

#include <cstddef>

namespace zawa {

template <class T>
struct dat {
	T value;
	std::size_t size;
	constexpr dat(const T& value = 0, const std::size_t& size = 0ULL) : value(value), size(size) {}
};

template <class T>
struct rangeAddMonoid {
	using valueType = dat<T>;
	static constexpr valueType identity{};
	static valueType operation(const valueType& a, const valueType& b) {
		return valueType(a.value + b.value, a.size + b.size);
	}
};

} // namespace zawa
#line 2 "src/utility/monoid/addMonoid.hpp"

namespace zawa {

template <class T>
struct addMonoid {
	using valueType = T;
	static constexpr valueType identity{};
	static valueType operation(const valueType& a, const valueType& b) {
		return a + b;
	}
};

} // namespace zawa
#line 6 "test/lazySquareDecomp-AOJ-RAQRSQ.test.cpp"

struct addAction {
	using valueMonoid = zawa::rangeAddMonoid<long long>;
	using operatorMonoid = zawa::addMonoid<long long>;
	static valueMonoid::valueType mapping(const valueMonoid::valueType& a, const operatorMonoid::valueType& b) {
		return valueMonoid::valueType(a.value + a.size * b, a.size);
	}
};

#include <iostream>
#line 17 "test/lazySquareDecomp-AOJ-RAQRSQ.test.cpp"

int main() {
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	int N, Q; std::cin >> N >> Q;
	zawa::lazySquareDecomp<addAction> sq(std::vector(N, addAction::valueMonoid::valueType(0LL, 1ULL)));
	for (int _ = 0 ; _ < Q ; _++) {
		int type; std::cin >> type;
		if (type == 0) {
			int s, t, x; std::cin >> s >> t >> x;
			sq.update(s - 1, t, x);
		}
		if (type == 1) {
			int s, t; std::cin >> s >> t;
			std::cout << sq.prod(s - 1, t).value << std::endl;
		}
	}
}
Back to top page