結果

問題 No.2395 区間二次変換一点取得
ユーザー ecotteaecottea
提出日時 2023-07-22 00:35:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 6,980 bytes
コンパイル時間 7,216 ms
コンパイル使用メモリ 320,752 KB
実行使用メモリ 28,264 KB
最終ジャッジ日時 2024-09-22 01:50:54
合計ジャッジ時間 11,517 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,752 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 18 ms
5,376 KB
testcase_12 AC 254 ms
5,456 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using mint = modint;
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i)


//【双対セグメント木（M-集合）】
/*
* Dual_segtree<S, F, act, comp, id>(vS v) : O(n)
*	配列 v[0..n) の要素で初期化する．
*	要素は左モノイド作用付き集合 (S, F, act, comp, id) の元とする．
*
* set(int i, S x) : O(log n)
*	v[i] = x とする．
*
* S get(int i) : O(log n)
*	v[i] を返す．
*
* apply(int l, int r, F f) : O(log n)
*	v[l..r) = f( v[l..r) ) とする．
*/
template <class S, class F, S(*act)(F, S), F(*comp)(F, F), F(*id)()>
class Dual_segtree {
	int actual_n; // 実際の要素数
	int n; // 完全二分木の葉の数（必ず 2 冪）

	// S の要素の格納用配列
	vector<S> v;

	// F の遅延評価用の完全二分木
	vector<F> lazy;

	// 遅延させていた評価を行う．：O(1)
	void eval(int k) {
		// 遅延させていた評価がなければ何もしない．
		if (lazy[k] == id()) return;

		// 子が居れば子に伝搬する．
		if (k < n / 2) {
			// 左作用を考えているのでこの向きに合成する．
			lazy[k * 2] = comp(lazy[k], lazy[k * 2]);
			lazy[k * 2 + 1] = comp(lazy[k], lazy[k * 2 + 1]);
		}
		// 葉なら遅延させずに v の要素に作用させてしまえばいい．
		else {
			v[k * 2 - n] = act(lazy[k], v[k * 2 - n]);
			v[k * 2 + 1 - n] = act(lazy[k], v[k * 2 + 1 - n]);
		}

		// 子への伝搬を終えたので自身は恒等写像になる．
		lazy[k] = id();
	}

	// k : 注目ノード，[kl..kr) : ノード v[k] が表す区間
	void set_sub(int i, S x, int k, int kl, int kr) {
		// 葉まで降りてきたら値を代入して帰る．
		if (kr - kl == 1) {
			v[k - n] = x;
			return;
		}

		// まず自身の評価を行っておく．
		eval(k);

		// 左右の子を見に行く．
		int km = (kl + kr) / 2;
		if (i < km) set_sub(i, x, k * 2, kl, km);
		else set_sub(i, x, k * 2 + 1, km, kr);
	}

	// k : 注目ノード，[kl..kr) : ノード v[k] が表す区間
	S get_sub(int i, int k, int kl, int kr) {
		// 葉まで降りてきたら値を返す．
		if (kr - kl == 1) return v[k - n];

		// まず自身の評価を行っておく．
		eval(k);

		// 左右の子を見に行く．
		int km = (kl + kr) / 2;
		if (i < km) return get_sub(i, k * 2, kl, km);
		else return get_sub(i, k * 2 + 1, km, kr);
	}

	// k : 注目ノード，[kl, kr) : ノード v[k] が表す区間
	void apply_sub(int l, int r, F f, int k, int kl, int kr) {
		// 範囲外なら何もしない．
		if (kr <= l || r <= kl) return;

		// 完全に範囲内なら自身の値を更新する．
		if (l <= kl && kr <= r) {
			if (kr - kl > 1) {
				// 左作用を考えているのでこの向きに合成する．
				lazy[k] = comp(f, lazy[k]);
			}
			else {
				v[k - n] = act(f, v[k - n]);
			}
			return;
		}

		// まず自身の評価を行っておく．
		eval(k);

		// 一部の範囲のみを含むなら子を見に行く．
		int km = (kl + kr) / 2;
		apply_sub(l, r, f, k * 2, kl, km);
		apply_sub(l, r, f, k * 2 + 1, km, kr);
	}

public:
	// 配列 v[0..n) の要素で初期化する．
	Dual_segtree(vector<S>& v_) : actual_n(v_.size()) {
		// verify : https://judge.yosupo.jp/problem/range_affine_point_get

		// 要素数以上となる最小の 2 冪を求め，n とする．
		n = 1 << (32 - __builtin_clz(actual_n - 1));

		// 配列の初期化
		v = v_;
		v.resize(n);
		lazy.assign(n, id());
	}

	// v[i] = x とする．
	void set(int i, S x) {
		set_sub(i, x, 1, 0, n);
	}

	// v[i] を返す．
	S get(int i) {
		// verify : https://judge.yosupo.jp/problem/range_affine_point_get

		return get_sub(i, 1, 0, n);
	}

	// v[l..r) = f( v[l..r) ) とする．
	void apply(int l, int r, F f) {
		// verify : https://judge.yosupo.jp/problem/range_affine_point_get

		if (l >= r) return;
		apply_sub(l, r, f, 1, 0, n);
	}
};


//【正方行列（固定サイズ）】
/*
* Fixed_matrix<T, n>() : O(n^2)
*	T の要素を成分にもつ n×n 零行列で初期化する．
*
* Fixed_matrix<T, n>(bool identity = true) : O(n^2)
*	T の要素を成分にもつ n×n 単位行列で初期化する．
*
* Fixed_matrix<T, n>(vvT a) : O(n^2)
*	二次元配列 a[0..n)[0..n) の要素で初期化する．
*
* A * x : O(n^2)
*	n×n 行列 A と n 次元列ベクトル array<T, n> x の積を返す．
*
* A * B : O(n^3)
*	n×n 行列 A と n×n 行列 B の積を返す．
*/
template <class T, int n>
struct Fixed_matrix {
	array<array<T, n>, n> v; // 行列の成分

	// n×n 零行列で初期化する．identity = true なら n×n 単位行列で初期化する．
	Fixed_matrix(bool identity = false) {
		rep(i, n) v[i].fill(T(0));
		if (identity) rep(i, n) v[i][i] = T(1);
	}

	// 二次元配列 a[0..n)[0..n) の要素で初期化する．
	Fixed_matrix(const vector<vector<T>>& a) {
		// verify : https://yukicoder.me/problems/no/1000

		rep(i, n) rep(j, n) v[i][j] = a[i][j];
	}

	// アクセス
	inline array<T, n> const& operator[](int i) const { return v[i]; }
	inline array<T, n>& operator[](int i) { return v[i]; }

	// 比較
	bool operator==(const Fixed_matrix& b) const { return v == b.v; }
	bool operator!=(const Fixed_matrix& b) const { return !(*this == b); }

	// 行列ベクトル積 : O(n^2)
	array<T, n> operator*(const array<T, n>& x) const {
		array<T, n> y{ 0 };
		rep(i, n) rep(j, n)	y[i] += v[i][j] * x[j];
		return y;
	}

	// 積：O(n^3)
	Fixed_matrix operator*(const Fixed_matrix& b) const {
		// verify : https://yukicoder.me/problems/no/1000

		Fixed_matrix res;
		rep(i, n) rep(j, n) rep(k, n) res[i][j] += v[i][k] * b[k][j];
		return res;
	}
	Fixed_matrix& operator*=(const Fixed_matrix& b) { *this = *this * b; return *this; }
};


//【行列乗算 左作用付き ベクトル 集合】
using T = mint;
using S = array<T, 5>;
using F = Fixed_matrix<T, 5>;
S act(F f, S x) { return f * x; }
F comp(F f, F g) { return f * g; } // これが重いので TLE する．
F id() { return Fixed_matrix<T, 5>(1); }
#define MatrixLMul_Vector_mset S, F, act, comp, id


int main() {
	int N, B, Q;
	cin >> N >> B >> Q;

	mint::set_mod(B);

	// 作用される側は 5 次元ベクトル (X, Y, Z, XZ, 1)，作用する側は 5×5 行列
	vector<S> ini(N, array<mint, 5>{1, 1, 1, 1, 1});
	Dual_segtree<MatrixLMul_Vector_mset> seg(ini);

	// 本問の操作はこの行列を掛けることに相当する．
	const F f(vector<vector<mint>>{
		{1,0,0,0,1},
		{0,3,2,2,0},
		{0,0,3,0,0},
		{0,0,3,3,0},
		{0,0,0,0,1}
	});

	while(Q--) {
		int l, m, r;
		cin >> l >> m >> r;
		l--; m--;

		// 区間 [l..r) 内のベクトルに行列を掛ける．
		seg.apply(l, r, f);

		// m 番目のベクトルを得る．
		auto [x, y, z, xz, one] = seg.get(m);

		cout << x.val() << " " << y.val() << " " << z.val() << endl;
	}
}
0