10pts求调
查看原帖
10pts求调
448018
KAqwq楼主2024/8/9 16:31
#include <bits/stdc++.h>
#define N 250005
#define mod 998244353
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1) 
#define Max_matrix 4

typedef long long LL;

LL n, m;

struct matrix {
	LL num[Max_matrix][Max_matrix];
	matrix(LL op = 0) {
		memset(num, 0, sizeof(num));
		if (op == 1) num[0][0] = num[1][1] = num[2][2] = num[3][3] = 1;
	}
//	inline void clear() memset(num, 0, sizeof num);
	LL* operator[](LL x) {return num[x];}
	matrix operator*(matrix b) {
		matrix c = matrix();
		for (LL i = 0; i < Max_matrix; ++i) {
			for (LL j = 0; j < Max_matrix; ++j) {
				for (LL k = 0; k < Max_matrix; ++k) {
					c[i][j] = (c[i][j] + (num[i][k] * b[k][j] % mod)) % mod;
				}
			}
		}
		return c;
	}//乘 
	matrix operator+(matrix b) {
		matrix c = matrix();
		for (LL i = 0; i < Max_matrix; ++i) {
			for (LL j = 0; j < Max_matrix; ++j) {
				c[i][j] = (num[i][j] + b[i][j]) % mod;
			}
		}
		return c;
	}//加 
}a[N];
struct tree {
	matrix sum, mul;
}t[N << 2];
inline void update(LL p) {
	t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
}
inline void build(LL l, LL r, LL p) {
	t[p].mul = matrix(1);
	if (l == r) {
		t[p].sum = a[l];
		return ;
	} 
	LL mid = l + ((r - l) >> 1);
	build(l, mid, ls(p));
	build(mid + 1, r, rs(p));
	update(p);
}
inline void pushdown(LL p) {
	t[ls(p)].sum = t[ls(p)].sum * t[p].mul, t[ls(p)].mul = t[ls(p)].mul * t[p].mul;
	t[rs(p)].sum = t[rs(p)].sum * t[p].mul, t[rs(p)].mul = t[rs(p)].mul * t[p].mul;
	t[p].mul = matrix(1);
}
inline void add(LL l, LL r, LL s, LL tt, LL p, matrix z) {
	if (l <= s && tt <= r) {
		t[p].sum = t[p].sum * z;
		t[p].mul = t[p].mul * z;
		return ; 
	}
	LL mid = s + ((tt - s) >> 1); pushdown(p);
	if (l <= mid) return add(l, r, s, mid, ls(p), z);
    if (r > mid) return add(l, r, mid + 1, tt, rs(p), z);
	update(p);
}
inline matrix query(LL l, LL r, LL s, LL tt, LL p) {
	if (l <= s && tt <= r) return t[p].sum;
	LL mid = s + ((tt - s) >> 1); pushdown(p);
	if (l <= mid) return query(l, r, s, mid, ls(p));
	if (r > mid) return query(l, r, mid + 1, tt, rs(p));
}
int main() {
	std::cin >> n;
	for (LL i = 1; i <= n; ++i) {
		std::cin >> a[i][0][0] >> a[i][0][1] >> a[i][0][2];
		a[i][0][3] = 1;
	}
	build(1, n, 1);
	std::cin >> m;
	while (m--) {
		matrix mt = matrix(1);
		LL opt, l, r, v; 
		std::cin >> opt;
		if (opt == 1) {
			std::cin >> l >> r;
			mt[1][0] = 1;
			add(1, n, l, r, 1, mt);
		} else if (opt == 2) {
			std::cin >> l >> r;
			mt[2][1] = 1;
			add(1, n, l, r, 1, mt);	
		} else if (opt == 3) {
			std::cin >> l >> r;
			mt[0][2] = 1;
			add(1, n, l, r, 1, mt);	
		} else if (opt == 4) {
			std::cin >> l >> r >> v;
			mt[3][0] = v;
			add(1, n, l, r, 1, mt);	
		} else if (opt == 5) {
			std::cin >> l >> r >> v;
			mt[1][1] = v;
			add(1, n, l, r, 1, mt);	
		} else if (opt == 6) {
			std::cin >> l >> r >> v;
			mt[2][2] = 0, mt[3][2] = v;
			add(1, n, l, r, 1, mt);	
		} else {
			std::cin >> l >> r;
			mt = query(1, n, l, r, 1);
			std::cout << mt[0][0] << ' ' << mt[0][1] << ' ' << mt[0][2] << '\n';
		}
	}
	return 0;
}
2024/8/9 16:31
加载中...