test/lazySquareDecomp-AOJ-RUQRmQ.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_F

Depends on

Code

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

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

using vM = zawa::minMonoid<int>;

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

struct action {
	using valueMonoid = vM;
	using operatorMonoid = oM;
	static const int mapping(const int& a, const int& b) {
		return b;
	}
};

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

#include <iostream>

int main() {
	int n, q; std::cin >> n >> q;
	zawa::lazySquareDecomp<action> sq(n);
	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) << std::endl;
		}
	}
}

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

#line 2 "src/utility/monoid/minMonoid.hpp"

#include <algorithm>
#include <limits>

namespace zawa {

template <class T>
struct minMonoid {
	using valueType = T;
	static constexpr valueType identity = std::numeric_limits<valueType>::max();
	static valueType operation(const valueType& a, const valueType& b) {
		return std::min(a, b);
	}
};

};
#line 4 "test/lazySquareDecomp-AOJ-RUQRmQ.test.cpp"

using vM = zawa::minMonoid<int>;

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

struct action {
	using valueMonoid = vM;
	using operatorMonoid = oM;
	static const int mapping(const int& a, const int& b) {
		return b;
	}
};

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

#include <vector>
#include <cmath>
#line 6 "src/dataStructure/lazySquareDecomp.hpp"

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-RUQRmQ.test.cpp"

#include <iostream>

int main() {
	int n, q; std::cin >> n >> q;
	zawa::lazySquareDecomp<action> sq(n);
	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) << std::endl;
		}
	}
}