洛谷P4340 [SHOI2016]随机序列

首先可以发现如果两个式子仅加号和减号互换的话，贡献仅为第一个加号或减号前面的表达式的值，于是我们枚举第一个+或-出现的位置，那么答案为

$$ \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;
}