verify/yosupo/yosupo-point_set_range_composite.test.cpp

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Problem: https://judge.yosupo.jp/problem/point_set_range_composite

Depends on

• library/contest/template-minimal.hpp
• library/data-structures/1d-range-queries/general-full-segment-tree.hpp
• library/math/affine.hpp
• library/modular-arithmetic/mod-int2.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/data-structures/1d-range-queries/general-full-segment-tree.hpp"
#include "../../library/modular-arithmetic/mod-int2.hpp"
#include "../../library/math/affine.hpp"

using mi = Mint<998244353, 5>;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	const Affine<mi> ID = {1, 0};
	auto comb = [&](Affine<mi> x, Affine<mi> y) {
		return x * y;
	};
	vector<Affine<mi>> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i].a >> v[i].b;
	}
	auto seg = get_lazy_segment_tree(
		v, ID, ID, comb, comb, comb
	);
	while (q--) {
		int t;
		cin >> t;
		if (t == 0) {
			int p, c, d;
			cin >> p >> c >> d;
			seg.set(p, {c, d});
		} else {
			int l, r, x;
			cin >> l >> r >> x;
			--r;
			auto res = seg.sum(l, r);
			cout << res(x) << '\n';
		}
	}
	return 0;
}

#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

template <class D, class L, class OpDD, class OpDL, class OpLL> struct LazySegmentTree {
	D e_d;
	L e_l;
	OpDD op_dd; 
	OpDL op_dl;
	OpLL op_ll;
	int sz, lg;  
	std::vector<D> d;
	std::vector<L> lz;

	void init(const std::vector<D>& v) {
		int n = int(v.size());
		lg = 1;
		while ((1 << lg) < n) lg++;
		sz = 1 << lg;
		d = std::vector<D>(2 * sz, e_d);
		lz = std::vector<L>(2 * sz, e_l);
		for (int i = 0; i < n; i++) d[sz + i] = v[i];
		for (int i = sz - 1; i >= 0; i--) {
			update(i);
		}
	}

	LazySegmentTree(const std::vector<D>& v,
			D _e_d,
			L _e_l,
			OpDD _op_dd,
			OpDL _op_dl,
			OpLL _op_ll)
		: e_d(_e_d), e_l(_e_l), op_dd(_op_dd), op_dl(_op_dl), op_ll(_op_ll) {
		init(v);
	}

	void all_add(int k, L x) {
		d[k] = op_dl(d[k], x);
		if (k < sz) lz[k] = op_ll(lz[k], x);
	}

	void push(int k) {
		all_add(2 * k, lz[k]);
		all_add(2 * k + 1, lz[k]);
		lz[k] = e_l;
	}

	void update(int k) { d[k] = op_dd(d[2 * k], d[2 * k + 1]); }

	void set(int p, D x) {
		p += sz;
		for (int i = lg; i >= 1; i--) push(p >> i);
		d[p] = x;
		for (int i = 1; i <= lg; i++) update(p >> i);
	}

	void add(int a, int b, L x, int l, int r, int k) {
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) {
			all_add(k, x);
			return;
		}
		push(k);
		int mid = (l + r) / 2;
		add(a, b, x, l, mid, 2 * k);
		add(a, b, x, mid, r, 2 * k + 1);
		update(k);
	}

	void add(int a, int b, L x) {
		++b;
		a += sz;
		b += sz;
		for (int i = lg; i >= 1; i--) {
			if (((a >> i) << i) != a) push(a >> i);
			if (((b >> i) << i) != b) push((b - 1) >> i);
		}
		{
			int a2 = a, b2 = b;
			while (a < b) {
				if (a & 1) all_add(a++, x);
				if (b & 1) all_add(--b, x);
				a >>= 1;
				b >>= 1;
			}
			a = a2;
			b = b2;
		}
		for (int i = 1; i <= lg; i++) {
			if (((a >> i) << i) != a) update(a >> i);
			if (((b >> i) << i) != b) update((b - 1) >> i);
		}
	}

	D single(int p) {
		p += sz;
		for (int i = lg; i >= 1; i--) push(p >> i);
		return d[p];
	}

	D sum(int a, int b, int l, int r, int k) {
		if (b <= l || r <= a) return e_d;
		if (a <= l && r <= b) return d[k];
		push(k);
		int mid = (l + r) / 2;
		return op_dd(sum(a, b, l, mid, 2 * k), sum(a, b, mid, r, 2 * k + 1));
	}

	D sum(int a, int b) {
		++b;
		if (a == b) return e_d;
		a += sz;
		b += sz;
		for (int i = lg; i >= 1; i--) {
			if (((a >> i) << i) != a) push(a >> i);
			if (((b >> i) << i) != b) push((b - 1) >> i);
		}
		D sml = e_d, smr = e_d;
		while (a < b) {
			if (a & 1) sml = op_dd(sml, d[a++]);
			if (b & 1) smr = op_dd(d[--b], smr);
			a >>= 1;
			b >>= 1;
		}
		return op_dd(sml, smr);
	}

	D all_sum() const { return d[1]; }
};

template <class D, class L, class OpDD, class OpDL, class OpLL>
LazySegmentTree<D, L, OpDD, OpDL, OpLL> get_lazy_segment_tree(std::vector<D> v,
										D e_d,
										L e_l,
										OpDD op_dd,
										OpDL op_dl,
										OpLL op_ll) {
	return LazySegmentTree<D, L, OpDD, OpDL, OpLL>(v, e_d, e_l, op_dd, op_dl, op_ll);
}

// 5 is a root of both mods

template <int MOD, int RT> struct Mint {
	static const int mod = MOD;
	static constexpr Mint rt() { return RT; } // primitive root for FFT

	static constexpr int md() { return MOD; } // primitive root for FFT

	int v; 
	explicit operator int() const { return v; } // explicit -> don't silently convert to int

	explicit operator bool() const { return v != 0; }
	Mint() { v = 0; }
	Mint(long long _v) { v = int((-MOD <= _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; }
	friend bool operator==(const Mint& a, const Mint& b) { return a.v == b.v; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.v < b.v; }
	friend bool operator>(const Mint& a, const Mint& b) { return a.v > b.v; }
	friend bool operator<=(const Mint& a, const Mint& b) { return a.v <= b.v; }
	friend bool operator>=(const Mint& a, const Mint& b) { return a.v >= b.v; }
	friend std::istream& operator >> (std::istream& in, Mint& a) { 
		long long x; std::cin >> x; a = Mint(x); return in; }
	friend std::ostream& operator << (std::ostream& os, const Mint& a) { return os << a.v; }
	Mint& operator+=(const Mint& m) { 
		if ((v += m.v) >= MOD) v -= MOD; 
		return *this; }
	Mint& operator-=(const Mint& m) { 
		if ((v -= m.v) < 0) v += MOD; 
		return *this; }
	Mint& operator*=(const Mint& m) { 
		v = (long long)v * m.v % MOD; return *this; }
	Mint& operator/=(const Mint& m) { return (*this) *= inv(m); }
	friend Mint pow(Mint a, long long p) {
		Mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
		return ans; 
	}
	friend Mint inv(const Mint& a) { assert(a.v != 0); return pow(a, MOD - 2); }
	Mint operator-() const { return Mint(-v); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
};

template <class T> struct Affine {
	T a, b;
	
	constexpr Affine() : a(1), b(0) {}
	constexpr Affine(T _a, T _b) : a(_a), b(_b) {}
	constexpr Affine(T _b) : a(0), b(_b) {}

	T operator()(T x) { return a * x + b; }
	
	Affine operator-() { return Affine(-a, -b); }
	
	friend Affine operator*(const Affine& l, const Affine& r) {
		return Affine(l.a * r.a, l.b * r.a + r.b); }
	friend Affine operator-(const Affine& l, const Affine& r) { return Affine(l.a - r.a, l.b - r.b); }
	friend Affine operator+(const Affine& l, const Affine& r) { return Affine(l.a + r.a, l.b + r.b); }
	
	friend Affine operator+(const Affine& l, const T& r) { return Affine(l.a, l.b + r); }
	friend Affine operator-(const Affine& l, const T& r) { return Affine(l.a, l.b - r); }
	friend Affine operator*(const Affine& l, const T& r) { return Affine(l.a * r, l.b * r); }
	friend Affine operator/(const Affine& l, const T& r) { return Affine(l.a / r, l.b / r); }

	friend Affine operator+(const T& l, Affine& r) { return r + l; }
	friend Affine operator-(const T& l, Affine& r) { return -r + l; }
	friend Affine operator*(const T& l, Affine& r) { return r * l; }
	
	friend Affine& operator+=(Affine& l, const Affine& r) { return l = l + r; }
	friend Affine& operator-=(Affine& l, const Affine& r) { return l = l - r; }
	friend Affine& operator*=(Affine& l, const Affine& r) { return l = l * r; }

	friend Affine& operator+=(Affine& l, const T& r) { return l = l + r; }
	friend Affine& operator-=(Affine& l, const T& r) { return l = l - r; }
	friend Affine& operator*=(Affine& l, const T& r) { return l = l * r; }

	bool operator==(const Affine& r) const { return a == r.a && b == r.b; }
	bool operator!=(const Affine& r) const { return a != r.a || b != r.b; }

	friend ostream& operator<<(ostream& os, const Affine& r) {
		os << "( " << r.a << ", " << r.b << " )"; return os; }
};

using mi = Mint<998244353, 5>;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	const Affine<mi> ID = {1, 0};
	auto comb = [&](Affine<mi> x, Affine<mi> y) {
		return x * y;
	};
	vector<Affine<mi>> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i].a >> v[i].b;
	}
	auto seg = get_lazy_segment_tree(
		v, ID, ID, comb, comb, comb
	);
	while (q--) {
		int t;
		cin >> t;
		if (t == 0) {
			int p, c, d;
			cin >> p >> c >> d;
			seg.set(p, {c, d});
		} else {
			int l, r, x;
			cin >> l >> r >> x;
			--r;
			auto res = seg.sum(l, r);
			cout << res(x) << '\n';
		}
	}
	return 0;
}

Back to top page