http://acm.hznu.edu.cn/OJ/problem.php?cid=1263&pid=5

http://acm.hznu.edu.cn/OJ/problem.php?id=2584

题意：设f[i]=max(f[i-1],s[i])，ans=∏min(m[i],f[i])，m[i]和f[i]可修改。

题解：

  线段树维护每个区间[l,r]且只考虑[l,r]的以下信息：

  fl,fr：f[l]和f[r]的值

  mul：∏min(m[i],f[i])

  rmul：将右儿子用左儿子的f修正后右儿子的贡献

  对于mul，有mul=左儿子的mul*ask(右儿子,左儿子的f[r])。

  其中ask(x,pre)表示考虑x的子树，之前f为pre时的乘积。

 

  若fl>=pre，则无需修正，直接返回mul即可。

  若x为叶子，则暴力处理即可。

  若左儿子的fr>=pre则右儿子只会被左儿子修正，返回ask(左儿子,pre)*mul。

  否则左儿子将全部被修正为pre，故返回ask(右儿子,pre)*左儿子全部修正为pre的贡献即可，贡献可以在每个节点上套上一棵Treap进行O(logn)计算。