mmrz's library

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

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

verify/aoj/dsl/2_I_Rupdate_Rsum.test.cpp

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_I

Depends on

• 遅延セグメント木 (data_structure/lazy_segment_tree.hpp)
• template/template.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_I"

#include "./../../../template/template.hpp"
#include "./../../../data_structure/lazy_segment_tree.hpp"

struct S{
	ll val;
	int size;
};
using F = ll;
constexpr F ID = -10000;

S op(S a, S b){ return {a.val+b.val, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){
	if(f != ID)x.val = f*x.size;
	return x;
}
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

void mmrz::solve(){
	int n, q;
	cin >> n >> q;

	vector<S> _v(n, {0, 1});
	lazy_segment_tree<S, op, e, F, mapping, composition, id> seg(_v);

	while(q--){
		int op;
		cin >> op;
		if(op == 0){
			int s, t, x;
			cin >> s >> t >> x;
			t++;
			seg.apply(s, t, x);
		}else{
			int s, t;
			cin >> s >> t;
			t++;
			cout << seg.fold(s, t).val << '\n';
		}
	}
}

#line 1 "verify/aoj/dsl/2_I_Rupdate_Rsum.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_I"

#line 1 "template/template.hpp"
# include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double pi = acos(-1);
template<class T>constexpr T inf() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T hinf() { return inf<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); }
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); }
template<class T> bool chmin(T& a,T b) { if(a > b){a = b; return true;} return false; }
template<class T> bool chmax(T& a,T b) { if(a < b){a = b; return true;} return false; }
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(ll n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(ll n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
ll gcd(ll a, ll b) { if (b == 0)return a; return gcd(b, a%b); };
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g*b; };
ll MOD(ll x, ll m){return (x%m+m)%m; }
ll FLOOR(ll x, ll m) {ll r = (x%m+m)%m; return (x-r)/m; }
template<class T> using dijk = priority_queue<T, vector<T>, greater<T>>;
# define all(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        (wpwpw).erase(unique(all((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(all((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(all((rprpr)),(rprpr).begin(),TU<char>)
# define rep(i,upupu)         for(ll i = 0, i##_len = (upupu);(i) < (i##_len);(i)++)
# define reps(i,opopo)        for(ll i = 1, i##_len = (opopo);(i) <= (i##_len);(i)++)
# define len(x)                ((ll)(x).size())
# define bit(n)               (1LL << (n))
# define pb push_back
# define eb emplace_back
# define exists(c, e)         ((c).find(e) != (c).end())

struct INIT{
	INIT(){
		std::ios::sync_with_stdio(false);
		std::cin.tie(0);
		cout << fixed << setprecision(20);
	}
}INIT;

namespace mmrz {
	void solve();
}

int main(){
	mmrz::solve();
}
#line 2 "data_structure/lazy_segment_tree.hpp"

#line 5 "data_structure/lazy_segment_tree.hpp"

template<class S, auto op, auto e, class F, auto mapping, auto composition, auto id>
struct lazy_segment_tree {
private:
	int n;
	int log;
	int size;
	std::vector<S> node;
	std::vector<F> lazy;

	void update(int k) { node[k] = op(node[2 * k], node[2 * k + 1]); }
	void all_apply(int k, F f) {
		node[k] = mapping(f, node[k]);
		if(k < size) lazy[k] = composition(f, lazy[k]);
	}
	void push(int k) {
		all_apply(2*k + 0, lazy[k]);
		all_apply(2*k + 1, lazy[k]);
		lazy[k] = id();
	}
public:
	lazy_segment_tree() : lazy_segment_tree(0) {}

	lazy_segment_tree(int _n) : lazy_segment_tree(std::vector<S>(_n, e())) {}

	lazy_segment_tree(const std::vector<S> &v) : n((int)v.size()) {
		size = 1;
		while(size < n) size <<= 1;

		log = __builtin_ctz(size);

		node.resize(2*size, e());
		lazy.resize(size, id());

		for(int i = 0;i < n;i++)node[i + size] = v[i];
		for(int i = size-1;i >= 1;i--)node[i] = op(node[2*i + 0], node[2*i + 1]);
	}

	void set(int x, S val) {
		assert(0 <= x && x < n);
		x += size;

		for(int i = log;i >= 1;i--)push(x >> i);
		node[x] = val;
		for(int i = 1;i <= log;i++)update(x >> i);
	}

	S operator[](int x) {
		assert(0 <= x && x < n);
		x += size;

		for(int i = log;i >= 1;i--)push(x >> i);
		return node[x];
	}

	S fold(int l, int r) {
		assert(0 <= l && l <= r && r <= n);
		if(l == r)return e();

		l += size;
		r += size;

		for(int i = log;i >= 1;i--) {
			if(((l >> i) << i) != l)push(l >> i);
			if(((r >> i) << i) != r)push((r-1) >> i);
		}

		S L = e(), R = e();
		for(;l < r;l >>= 1, r >>= 1){
			if(l&1)L = op(L, node[l++]);
			if(r&1)R = op(node[--r], R);
		}
		return op(L, R);
	}

	S all_fold() { return node[1]; };

	void apply(int x, F f) {
		assert(0 <= x && x < n);

		x += size;
		for(int i = log;i >= 1;i--)push(x >> i);
		node[x] = mapping(f, node[x]);
		for(int i = 1;i <= log;i++)update(x >> i);
	}

	void apply(int l, int r, F f) {
		assert(0 <= l && l <= r && r <= n);
		if(l == r)return;

		l += size;
		r += size;

		for(int i = log;i >= 1;i--) {
			if(((l >> i) << i) != l)push(l >> i);
			if(((r >> i) << i) != r)push((r-1) >> i);
		}

		{
			int l2 = l, r2 = r;
			while (l < r) {
				if (l & 1) all_apply(l++, f);
				if (r & 1) all_apply(--r, f);
				l >>= 1;
				r >>= 1;
			}
			l = l2;
			r = r2;
		}

		for (int i = 1; i <= log; i++) {
			if (((l >> i) << i) != l) update(l >> i);
			if (((r >> i) << i) != r) update((r - 1) >> i);
		}
	}

	template<bool (*g)(S)> int max_right(int l) {
		return max_right(l, [](S x){ return g(x); });
	}
	template<class G> int max_right(int l, G g) {
		assert(0 <= l && l <= n);
		assert(g(e()));

		if(l == n)return n;

		l += size;
		for(int i = log;i >= 1;i--)push(l >> i);

		S sum = e();
		do {
			while(l%2 == 0)l >>= 1;
			if(not g(op(sum, node[l]))) {
				while(l < size) {
					push(l);
					l <<= 1;
					if(g(op(sum, node[l]))) {
						sum = op(sum, node[l]);
						l++;
					}
				}
				return l-size;
			}
			sum = op(sum, node[l]);
			l++;
		}while((l&-l) != l);
		return n;
	}

	template <bool (*g)(S)> int min_left(int r) {
		return min_left(r, [](S x) { return g(x); });
	}
	template<class G> int min_left(int r, G g) {
		assert(0 <= r && r <= n);
		assert(g(e()));

		if(r == 0)return 0;

		r += size;
		for(int i = log;i >= 1;i--)push((r-1) >> i);

		S sum = e();
		do {
			r--;
			while(r > 1 && (r%2))r >>= 1;
			if(not g(op(node[r], sum))) {
				while(r < size) {
					push(r);
					r = r*2 + 1;
					if(g(op(node[r], sum))) {
						sum = op(node[r], sum);
						r--;
					}
				}
				return r+1-size;
			}
			sum = op(node[r], sum);
		}while((r&-r) != r);
		return 0;
	}
};
#line 5 "verify/aoj/dsl/2_I_Rupdate_Rsum.test.cpp"

struct S{
	ll val;
	int size;
};
using F = ll;
constexpr F ID = -10000;

S op(S a, S b){ return {a.val+b.val, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){
	if(f != ID)x.val = f*x.size;
	return x;
}
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

void mmrz::solve(){
	int n, q;
	cin >> n >> q;

	vector<S> _v(n, {0, 1});
	lazy_segment_tree<S, op, e, F, mapping, composition, id> seg(_v);

	while(q--){
		int op;
		cin >> op;
		if(op == 0){
			int s, t, x;
			cin >> s >> t >> x;
			t++;
			seg.apply(s, t, x);
		}else{
			int s, t;
			cin >> s >> t;
			t++;
			cout << seg.fold(s, t).val << '\n';
		}
	}
}

Back to top page