2020牛客寒假算法基础集训营2——J-求函数【线段树 维护 矩阵乘法】【函数推导 + 双线段树维护参数】

2020牛客寒假算法基础集训营2——J-求函数【线段树 维护 矩阵乘法】【函数推导 + 双线段树维护参数】

​​题目传送门​​

题目描述

输入描述:

输出描述:

对于每个求值操作，输出一行一个整数，表示答案。

输入

2 3 1 1 1 0 1 2 114514 1919810 2 1 2 2 1 1

输出

2148838 2

说明

AC-Code

#include using namespace std;typedef long long ll;#defineconst int maxn = 2e5 + 5;const int mod = 1e9 + 7;int k[maxn];int b[maxn];struct Mat { ll m[2][2]; int left, right; Mat() { memset(m, 0, sizeof m); } // 注意初始化m数组，处理下随机值 friend Mat operator * (const Mat& a, const Mat& b) { Mat res; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) { for (int k = 0; k < 2; ++k) res.m[i][j] += (a.m[i][k] * b.m[k][j]) % mod; res.m[i][j] %= mod; } return res; }};struct SegTree {#define Mat tree[maxn << 2]; void PushUp(int rt) { int l = tree[rt].left; // 由于Mat里存储了l、r，乘法操作的时候返回新的Mat，导致l，r丢失，预先存起来，避免l、r不见了 int r = tree[rt].right; tree[rt] = tree[rt << 1] * tree[rt << 1 | 1]; tree[rt].left = l; tree[rt].right = r; } void build(int rt, int l, int r) { tree[rt].left = l; tree[rt].right = r; if (l == r) { tree[rt].m[0][0] = k[l]; tree[rt].m[1][0] = b[r]; tree[rt].m[1][1] = 1; return; } build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); PushUp(rt); } void update(int rt, int pos) { if (tree[rt].left == tree[rt].right) { tree[rt].m[0][0] = k[tree[rt].left]; tree[rt].m[1][0] = b[tree[rt].right]; return; } int md = (tree[rt].left + tree[rt].right) >> 1; if (pos <= md) update(rt << 1, pos); else update(rt << 1 | 1, pos); PushUp(rt); } Mat query(int rt, int l, int r) { if (l <= tree[rt].left && tree[rt].right <= r) return tree[rt]; Mat res; res.m[0][0] = res.m[1][1] = 1; // 初始化为单位阵 int md = (tree[rt].left + tree[rt].right) >> 1; if (l <= md) res = res * query(rt << 1, l, r); if (r > md) res = res * query(rt << 1 | 1, l, r); return res; }#undef};SegTree st;int main() { ios; int n, m; while (cin >> n >> m) { for (int i = 1; i <= n; ++i) cin >> k[i]; for (int i = 1; i <= n; ++i) cin >> b[i]; st.build(1, 1, n); while (m--) { int x, i, k, b, l, r; cin >> x; Mat ans; ans.m[0][0] = ans.m[0][1] = 1; if (x & 1) { cin >> i >> k >> b; ::k[i] = k % mod, ::b[i] = b % mod; st.update(1, i); } else { cin >> l >> r; ans = ans * st.query(1, l, r); cout << ans.m[0][0] << endl; } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。