这道题的题意就是给你n个数让你在每个数之间插入+、-、*三种运算符中的一种，然后算出一个答案，再把答案加起来。
这题肯定是不能暴力的(题目都告诉你了由3n-1种结果)。我们先从小的情况枚举找一找规律。
n=1
a1
n=2
2*a1+a1*a2
n=3
6*a1+2*a1*a2+a1*a2*a3
n=4
18*a1+6*a1*a2+2a1*a2*a3+a1*a2*a3*a4
发现没有？每一项是一个前缀积，每一项的系数除了最后两项都是后一项*3。这样我们就可以拿线段树维护这个答案了。
每次改我们就在[k, n]这个区间*a[k]的逆*v(除a[k]乘v)，在求一下[1, n]的和就是答案了。
别忘了要把a[k]赋成v。
#include <iostream> #include <cstdio> using namespace std; typedef long long ll; const ll N = 100010; const ll mod = 1000000007; ll n, Q; ll a[N], mul[N]; struct Segment_Tree{ ll val, tag; }st[N << 2]; ll ksm(ll x, ll y) { ll ret = 1; while (y) { if (y & 1) ret = (ret * x) % mod; y >>= 1; x = (x * x) % mod; } return ret; } void build(ll x, ll l, ll r) { st[x].tag = 1; if (l == r) { if (l == n) { st[x].val = mul[n] % mod; } else if (l == n - 1) { st[x].val = (2 * mul[n - 1]) % mod; } else { st[x].val = (((ksm(3, n - l - 1) * 2) % mod) * mul[l]) % mod; } return; } ll mid = (l + r) >> 1; build(x << 1, l, mid); build(x << 1 | 1, mid + 1, r); st[x].val = (st[x << 1].val + st[x << 1 | 1].val) % mod; } void push_down(ll x) { if (st[x].tag != 1) { st[x << 1].tag = (st[x].tag * st[x << 1].tag) % mod; st[x << 1].val = (st[x].tag * st[x << 1].val) % mod; st[x << 1 | 1].tag = (st[x].tag * st[x << 1 | 1].tag) % mod; st[x << 1 | 1].val = (st[x].tag * st[x << 1 | 1].val) % mod; st[x].tag = 1; } } void change(ll x, ll l, ll r, ll p, ll q, ll v) { if (r < p || l > q) return; if (p <= l && r <= q) { st[x].tag = (st[x].tag * v) % mod; st[x].val = (st[x].val * v) % mod;; return; } push_down(x); ll mid = (l + r) >> 1; change(x << 1, l, mid, p, q, v); change(x << 1 | 1, mid + 1, r, p, q, v); st[x].val = (st[x << 1].val + st[x << 1 | 1].val) % mod; } ll read() { ll ret = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { ret = (ret << 1) + (ret << 3) + ch - '0'; ch = getchar(); } return ret * f; } int main() { mul[0] = 1; n = read(), Q = read(); for (ll i = 1; i <= n; i++) { a[i] = read(); mul[i] = (mul[i - 1] * a[i]) % mod; } build(1, 1, n); while (Q--) { ll t, v; t = read(), v = read(); change(1, 1, n, t, n, (ksm(a[t], mod - 2) * v) % mod); cout << st[1].val << " "; a[t] = v; } return 0; }