test/datastructure/segment_tree/yosupo_point_set_range_composite.test.cpp

• View this file on GitHub
• Last update: 2023-12-14 18:25:11+09:00
• Problem: https://judge.yosupo.jp/problem/point_set_range_composite

Depends on

• Segment tree (src/datastructure/segment_tree.hpp)

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/point_set_range_composite

#include "src/datastructure/segment_tree.hpp"

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int const MOD = 998244353;

int main() {
	int n, q;
	cin >> n >> q;
	vector<pair<long long, long long>> ab(n);
	for (auto &[a, b] : ab) cin >> a >> b;

	auto f = [](pair<long long, long long> a, pair<long long, long long> b) {
		return pair(b.first * a.first % MOD,
					(b.first * a.second % MOD + b.second) % MOD);
	};
	SegmentTree seg(f, pair<long long, long long>{1LL, 0LL});
	seg.init(n);
	seg.build(ab);

	while (q--) {
		int com;
		cin >> com;
		if (com) {
			int l, r, x;
			cin >> l >> r >> x;
			auto [a, b] = seg.find(l, r);
			cout << (a * x % MOD + b) % MOD << endl;
		} else {
			int p, c, d;
			cin >> p >> c >> d;
			seg.update(p, {c, d});
		}
	}

	return 0;
}

#line 1 "test/datastructure/segment_tree/yosupo_point_set_range_composite.test.cpp"
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/point_set_range_composite

#line 1 "src/datastructure/segment_tree.hpp"



#include <vector>

template<class T, class F>
class SegmentTree { // 0-indexed
private:
	int n_{};
	std::vector<T> tree;
	F f; // function<T(T, T)>
	T ti;

public:
	SegmentTree(F f, T ti) : f(f), ti(ti) {}

	void init(int n) {
		n_ = 1;
		while (n_ < n) n_ *= 2;
		tree.assign(2 * n_, ti);
	}

	void build(std::vector<T> const &v) {
		int const N = v.size();
		init(N);
		for (int i = 0; i < N; ++i) tree[n_ + i] = v[i];
		for (int i = n_ - 1; i > 0; --i) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
	}

	void update(int i, T const &x) {
		i += n_;
		tree[i] = x;
		while (i >>= 1) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
	}

	T find(int l, int r) { // [l, r)
		l += n_, r += n_;
		T ll = ti, rr = ti;
		while (l < r) {
			if (l & 1) ll = f(ll, tree[l++]);
			if (r & 1) rr = f(tree[--r], rr);
			l >>= 1, r >>= 1;
		}
		return f(ll, rr);
	}

	T at(int i) { return tree[i + n_]; }
};


#line 4 "test/datastructure/segment_tree/yosupo_point_set_range_composite.test.cpp"

#include <iostream>
#include <utility>
#line 8 "test/datastructure/segment_tree/yosupo_point_set_range_composite.test.cpp"

using namespace std;

int const MOD = 998244353;

int main() {
	int n, q;
	cin >> n >> q;
	vector<pair<long long, long long>> ab(n);
	for (auto &[a, b] : ab) cin >> a >> b;

	auto f = [](pair<long long, long long> a, pair<long long, long long> b) {
		return pair(b.first * a.first % MOD,
					(b.first * a.second % MOD + b.second) % MOD);
	};
	SegmentTree seg(f, pair<long long, long long>{1LL, 0LL});
	seg.init(n);
	seg.build(ab);

	while (q--) {
		int com;
		cin >> com;
		if (com) {
			int l, r, x;
			cin >> l >> r >> x;
			auto [a, b] = seg.find(l, r);
			cout << (a * x % MOD + b) % MOD << endl;
		} else {
			int p, c, d;
			cin >> p >> c >> d;
			seg.update(p, {c, d});
		}
	}

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	13 ms	7 MB
g++	max_random_00	AC	1375 ms	34 MB
g++	max_random_01	AC	1360 ms	34 MB
g++	max_random_02	AC	1330 ms	34 MB
g++	max_random_03	AC	1370 ms	34 MB
g++	max_random_04	AC	1457 ms	34 MB
g++	random_00	AC	1285 ms	32 MB
g++	random_01	AC	1134 ms	33 MB
g++	random_02	AC	912 ms	10 MB
g++	random_03	AC	371 ms	33 MB
g++	random_04	AC	499 ms	30 MB
g++	small_00	AC	16 ms	7 MB
g++	small_01	AC	15 ms	7 MB
g++	small_02	AC	16 ms	7 MB
g++	small_03	AC	14 ms	7 MB
g++	small_04	AC	14 ms	7 MB
clang++	example_00	AC	12 ms	15 MB
clang++	max_random_00	AC	1465 ms	38 MB
clang++	max_random_01	AC	1448 ms	36 MB
clang++	max_random_02	AC	1602 ms	36 MB
clang++	max_random_03	AC	1423 ms	38 MB
clang++	max_random_04	AC	1483 ms	36 MB
clang++	random_00	AC	1197 ms	36 MB
clang++	random_01	AC	1207 ms	36 MB
clang++	random_02	AC	771 ms	10 MB
clang++	random_03	AC	402 ms	35 MB
clang++	random_04	AC	577 ms	35 MB
clang++	small_00	AC	16 ms	13 MB
clang++	small_01	AC	15 ms	13 MB
clang++	small_02	AC	15 ms	13 MB
clang++	small_03	AC	15 ms	11 MB
clang++	small_04	AC	15 ms	13 MB

Back to top page