题目：https://hihocoder.com/problemset/problem/1116
现在有一个有n个元素的数组a1, a2, ..., an。
记f(i, j) = ai * ai+1 * ... * aj。
初始时，a1 = a2 = ... = an = 0，每次我会修改一个ai的值，你需要实时反馈给我 ∑1 <= i <= j <= n f(i, j)的值 mod 10007。
第一行包含两个数n(1<=n<=100000)和q(1<=q<=500000)。
接下来q行，每行包含两个数i, x，代表我把ai的值改为了x。
分别输出对应的答案，一个答案占一行。
样例输入
5 5 1 1 2 1 3 1 4 1 5 1样例输出
1 3 6 10 15题意：
求区间（1，n）的所有子区间的连乘的和；
思路：
线段数，这题如果用用线段树做不会的会可能就是不会合并两个区间；
对于线段树的每一个节点，我们保持这个区间的答案（ans），前缀连乘和（ls），后缀连乘和，以及连乘（mul）；
对于每个节点我们可以这样合并：
至于为什么可以这样，自己举两三个数来看一看就很清楚了；
#include<bits/stdc++.h> using namespace std; #define mod 10007 const int maxn = 100 * 1000 + 10; int n,q; struct { struct { int L, R; int ls, rs, mul, ans; }tree[maxn<<2]; void join(int rt) { tree[rt].ans = (tree[rt << 1].ans + tree[rt << 1 | 1].ans + tree[rt << 1].rs*tree[rt << 1 | 1].ls) % mod; tree[rt].ls = (tree[rt<<1].ls + tree[rt << 1].mul*tree[rt << 1 | 1].ls) % mod; tree[rt].rs = (tree[rt<<1|1].rs + tree[rt << 1|1].mul*tree[rt << 1].rs) % mod; tree[rt].mul = (tree[rt << 1].mul*tree[rt<<1|1].mul)%mod; } void build(int s,int L,int R) { tree[s].L = L; tree[s].R = R; tree[s].ls = tree[s].rs = tree[s].ans = tree[s].ans = 0; if (L == R)return; int mid = (L + R)>>1; build(s<<1,L,mid); build(s<<1|1,mid+1,R); } void change(int rt, int pos,int x) { if (tree[rt].L==tree[rt].R) { tree[rt].ls = tree[rt].rs = tree[rt].mul = tree[rt].ans = x; return; } int mid = (tree[rt].L + tree[rt].R) >> 1; if (pos <= mid)change(rt<<1,pos,x); else change(rt << 1 | 1, pos, x); join(rt); } }T; int main() { ios::sync_with_stdio(false); cin >> n >> q; int p, x; T.build(1,1,n); while (q--) { cin >> p >> x; T.change(1,p,x); cout << T.tree[1].ans<<endl; } return 0; }
