結果

問題 No.2395 区間二次変換一点取得
ユーザー ecotteaecottea
提出日時 2023-07-22 00:50:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 565 ms / 2,000 ms
コード長 8,151 bytes
コンパイル時間 6,848 ms
コンパイル使用メモリ 311,364 KB
実行使用メモリ 11,112 KB
最終ジャッジ日時 2024-09-22 02:03:37
合計ジャッジ時間 11,888 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,376 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 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 5 ms
5,376 KB
testcase_12 AC 43 ms
5,376 KB
testcase_13 AC 565 ms
11,112 KB
testcase_14 AC 558 ms
11,112 KB
testcase_15 AC 542 ms
11,032 KB
testcase_16 AC 548 ms
11,048 KB
testcase_17 AC 542 ms
11,108 KB
testcase_18 AC 342 ms
10,880 KB
testcase_19 AC 338 ms
11,108 KB
権限があれば一括ダウンロードができます

ソースコード

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; }
};


//【行列乗算 左作用付き ベクトル 集合】（の改変）
/*
方針は https://yukicoder.me/submissions/894429 の方がわかりやすいと思う．
上記提出では行列と行列の積が重くて TLE したので，必要な成分だけをベタ書きする．
手動でやると大変だが，Wolfram Alpha を使えば，
　入力：
　{{a,0,0,0,b},{0,c,d,e,0},{0,0,f,0,0},{0,0,g,h,0},{0,0,0,0,1}}.{x,y,z,w,1}
　出力：
　(b + a x, e w + c y + d z, f z, h w + g z, 1)
および
　入力：
　{{a,0,0,0,b},{0,c,d,e,0},{0,0,f,0,0},{0,0,g,h,0},{0,0,0,0,1}}.{{i,0,0,0,j},{0,k,l,m,0},{0,0,n,0,0},{0,0,o,p,0},{0,0,0,0,1}}
　出力：
　{{a i, 0, 0, 0, b + a j}, {0, c k, c l + d n + e o, c m + e p, 0}, {0, 0, f n, 0, 0}, {0, 0, g n + h o, h p, 0}, {0, 0, 0, 0, 1}}
が得られるので，適当に整形すればいい．

同じテクニックを使える問題：ABC256F
自分の提出：https://atcoder.jp/contests/abc256/submissions/32562498
*/
using S = array<mint, 4>;
using F = array<mint, 8>;
S act(F tmpF, S tmpS) {
	auto [a, b, c, d, e, f, g, h] = tmpF;
	auto [x, y, z, w] = tmpS;
	return { b + a * x, e * w + c * y + d * z, f * z, h * w + g * z };
}
F comp(F tmpF, F tmpF2) {
	auto [a, b, c, d, e, f, g, h] = tmpF;
	auto [i, j, k, l, m, n, o, p] = tmpF2;

	return { a * i, b + a * j, c * k, c * l + d * n + e * o, c * m + e * p, f * n, g * n + h * o, h * p };
}
F id() {
	return { 1, 0, 1, 0, 0, 1, 0, 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, S{1, 1, 1, 1});
	Dual_segtree<MatrixLMul_Vector_mset> seg(ini);

	// 本問の操作はこの行列を掛けることに相当する．
	F f = { 1, 1, 3, 2, 2, 3, 3, 3 };
	// { 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] = seg.get(m);

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