线段树（区间合并）

题目：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;
}