test/lazySquareDecomp-AOJ-RUQRSQ.test.cpp

View this file on GitHub
Last update: 2023-03-10 16:33:31+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_I

Depends on

Code

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

#include "../src/utility/monoid/rangeAddMonoid.hpp"

using vM = zawa::rangeAddMonoid<long long>;

struct oM {
	using valueType = long long;
	static constexpr valueType identity = -1001;
	static valueType operation(const valueType& a, const valueType& b) {
		return b;
	}
};

struct action {
	using valueMonoid = vM;
	using operatorMonoid = oM;
	static vM::valueType mapping(const vM::valueType& a, const long long& b) {
		return vM::valueType(a.size * b, a.size);
	}
};

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

#include <iostream>
#include <vector>

int main() {
	int n, q; std::cin >> n >> q;
	zawa::lazySquareDecomp<action> sq(std::vector(n, vM::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, t + 1, x);
		}
		if (type == 1) {
			int s, t; std::cin >> s >> t;
			std::cout << sq.prod(s, t + 1).value << std::endl;
		}
	}
}

#line 1 "test/lazySquareDecomp-AOJ-RUQRSQ.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_I"

#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 4 "test/lazySquareDecomp-AOJ-RUQRSQ.test.cpp"

using vM = zawa::rangeAddMonoid<long long>;

struct oM {
	using valueType = long long;
	static constexpr valueType identity = -1001;
	static valueType operation(const valueType& a, const valueType& b) {
		return b;
	}
};

struct action {
	using valueMonoid = vM;
	using operatorMonoid = oM;
	static vM::valueType mapping(const vM::valueType& a, const long long& b) {
		return vM::valueType(a.size * b, a.size);
	}
};

#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 24 "test/lazySquareDecomp-AOJ-RUQRSQ.test.cpp"

#include <iostream>
#line 27 "test/lazySquareDecomp-AOJ-RUQRSQ.test.cpp"

int main() {
	int n, q; std::cin >> n >> q;
	zawa::lazySquareDecomp<action> sq(std::vector(n, vM::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, t + 1, x);
		}
		if (type == 1) {
			int s, t; std::cin >> s >> t;
			std::cout << sq.prod(s, t + 1).value << std::endl;
		}
	}
}