群论

题意简述

给定长为 $n$ 的序列 $a$。要求支持以下操作：

• 给定 $l,r,x$，将 $a_i,l\leq i\leq r$ 全部加上 $x$；
• 给定 $l,r,x$，将 $a_i,l\leq i\leq r$ 全部乘以 $x$；
• 给定 $l,r,x$，若这是第 $k$ 次操作，则保护 $a_i,l\leq i\leq r$ 直到第 $k+x$ 次操作（含），这期间操作 $1,2$ 对 $a_i$ 无效。若 $a_i$ 已经被保护到 $x’,x’>k+x$，则这一保护不会失效。
• 给定 $l,r$，输出 $\sum_{i=l}^{r} a_i$，对 $10^9+7$ 取余。

$n,m\leq 2\times 10^5$。

半群、双半群模型——线段树到底能维护怎样的信息？——caijianhong 的博客园

（更多…）