結果

問題 No.3227 Matrix Query
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-07-29 01:04:15
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 760 ms / 8,000 ms
コード長 2,733 bytes
コンパイル時間 2,141 ms
コンパイル使用メモリ 131,592 KB
実行使用メモリ 12,776 KB
最終ジャッジ日時 2025-07-30 16:20:22
合計ジャッジ時間 17,851 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.algorithm, std.array, std.conv, std.typecons;

void main() {
	long K, N;
	{
		auto tmp = readln.split.to!(long[]);
		K = tmp[0], N = tmp[1];
	}
	
	auto A = new Matrix[N];
	foreach (n; 0 .. N) {
		auto row0 = readln.split.to!(long[]),
		     row1 = readln.split.to!(long[]);
		Matrix M;
		M[0][0] = row0[0]%K, M[0][1] = row0[1]%K, 
		M[1][0] = row1[0]%K, M[1][1] = row1[1]%K, 
		A[n] = M;
	}
	
	auto Q = readln[0 .. $-1].to!long;
	auto I = new ulong[Q], Y = new Matrix[Q], L = new ulong[Q], R = new ulong[Q];
	foreach (q; 0 .. Q) {
		auto tmp = readln.split.to!(ulong[]);
		I[q] = tmp[0], L[q] = tmp[1], R[q] = tmp[2];
		
		auto row0 = readln.split.to!(long[]),
		     row1 = readln.split.to!(long[]);
		Matrix M;
		M[0][0] = row0[0]%K, M[0][1] = row0[1]%K, 
		M[1][0] = row1[0]%K, M[1][1] = row1[1]%K, 
		Y[q] = M;
	}
	
	/****************************************
	*****************************************/
	
	auto size = 1;
	while (size < N) size *= 2;
	
	auto tree = new SegTree(size, K);
	foreach (n, mat; A)
		tree.update(n, mat);
	
	foreach (q; 0 .. Q) {
		tree.update(I[q]-1, Y[q]);
		auto mat = tree.query(L[q]-1, R[q]);
		mat[0][0] += mat[0][0] < 0 ? K : 0,
		mat[1][0] += mat[1][0] < 0 ? K : 0,
		mat[0][1] += mat[0][1] < 0 ? K : 0,
		mat[1][1] += mat[1][1] < 0 ? K : 0,
		writefln("%d %d\n%d %d", mat[0][0], mat[0][1], mat[1][0], mat[1][1]);
	}
}

alias Matrix = long[2][2];

Matrix multiply(Matrix a, Matrix b, long mod) {
	Matrix c;
	c[0][0] = (a[0][0]*b[0][0] + a[0][1]*b[1][0])%mod, c[0][1] = (a[0][0]*b[0][1] + a[0][1]*b[1][1])%mod,
	c[1][0] = (a[1][0]*b[0][0] + a[1][1]*b[1][0])%mod, c[1][1] = (a[1][0]*b[0][1] + a[1][1]*b[1][1])%mod;
	return c;
}

class SegTree {
	ulong size;
	long mod;
	Matrix[] mats;
	
	this (ulong size, long mod) {
		this.size = size;
		this.mod = mod;
		mats.length = 2*size-1;
		// set to identity
		foreach (n; 0 .. 2*size-1) {
			mats[n][0][0] = 1, mats[n][0][1] = 0,
			mats[n][1][0] = 0, mats[n][1][1] = 1;
		}
	}
	
	void update(ulong i, Matrix mat) {
		assert(i < size);
		i += size-1;
		mats[i] = mat;
		while (i > 0) {
			i = (i-1)/2;		// parent
			mats[i] = multiply(mats[2*i+1], mats[2*i+2], mod);
		}
	}
	
	// return the product of matrices in [a, b)
	Matrix query(ulong a, ulong b) {
		return _query(a, b, 0, 0, size);
	}
	
	// k-th node is the interval [l, r)
	Matrix _query(ulong a, ulong b, ulong k, ulong l, ulong r) {
		// out of interval
		if (r <= a || b <= l)
			return
				[ [1, 0],
				  [0, 1] ];
			
		// [l, r) is contained in [a, b)
		else if (a <= l && r <= b)
			return mats[k];
		// intersects
		else
			return multiply(
				_query(a, b, 2*k+1, l, (l+r)/2),	// left child
				_query(a, b, 2*k+2, (l+r)/2, r),	// right child
				mod
			);
	}
}
0