首先可以发现如果两个式子仅加号和减号互换的话,贡献仅为第一个加号或减号前面的表达式的值,于是我们枚举第一个+或-出现的位置,那么答案为
$$ \sum_{i = 1}^{n - 1}\left(\prod_{k = 1}^{i}a_i \times 2 \times 3^{n - i + 1}\right) + \prod_{k = 1}^{n}a_i $$
因为要支持单点修改,考虑线段树维护这一个答案,其实这个式子在维护一个前缀积的前缀和,对于合并两个区间,合并完的右半部分的答案可以提取公因数,公因数为为左区间的累积,提取公因数后剩下的为右区间的答案
若该题没有出现$0$修改成正数的操作的话,还可以转化为叶子节点维护前缀积,线段树维护和,每次对区间$(x,n)$乘$x$位置上的数的逆元再乘上要修改的数即可
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
void file() {
freopen("std.in", "r", stdin);
freopen("wa.out", "w", stdout);
}
const int N = 1e6 + 10, inf = 1e9, dsq = 1e9 + 7;
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int n, m, a[N], m3[N];
namespace SEG {
int ans[N], mul[N];
#define ls x << 1
#define rs x << 1 | 1
void pushup(int x) {
mul[x] = 1ll * mul[ls] * mul[rs] % dsq;
ans[x] = (ans[ls] + 1ll * ans[rs] * mul[ls] % dsq) % dsq;
}
void build(int x, int l, int r) {
if (l == r) {
mul[x] = a[l]; if (l == n) ans[x] = a[l]; else ans[x] = 2ll * a[l] * m3[n - l - 1] % dsq;
return;
}
int mid = l + r >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
pushup(x);
}
void modify(int x, int l, int r, int pos, int t) {
if (l == r) {
mul[x] = t; if (l == n) ans[x] = t; else ans[x] = 2ll * t * m3[n - l - 1] % dsq;
return;
}
int mid = l + r >> 1;
if (mid >= pos) modify(ls, l, mid, pos, t);
else modify(rs, mid + 1, r, pos, t);
pushup(x);
}
}
int main() {
n = read(); m = read(); m3[0] = 1;
for (int i = 1; i <= n; i++) a[i] = read(), m3[i] = 3ll * m3[i - 1] % dsq;
using namespace SEG; build(1, 1, n);
for (int i = 1; i <= m; i++) {
int x = read(), t = read();
modify(1, 1, n, x, t); printf("%d\n", ans[1]);
}
return 0;
}