题目大意
\(n\)个数,对这些数进行\(t\times q\)次操作,操作有单点修改、全局加、全局乘、全局修改、单点询问、全局求和这几种。
\(t\times q\)次操作中,每次操作都是来自于给出的\(q\)次基本操作之一。输出所有询问操作的和模\(10^7+19\)。
\(n\leq 10^9;q\leq 10^5;t\leq 100;-10^9\leq 操作中涉及的值 \leq 10^9\)
题解
只用存\(\leq 10^5\)个单点修改操作涉及的点。
正常的做法:维护全局加标记、乘标记、修改标记,单点修改时将这个点的值改为\((值+加法逆元)\times 乘法逆元\)。
并不对劲的做法:维护每个时刻的加标记、乘标记、修改标记、每个点上次修改的时刻,单点查询时,如果该点上次的修改操作是单点修改,值=\((修改的数\times 当前乘标记\times修改时乘标记的逆元)+(当前加标记+修改时加标记的逆元\times(当前乘标记\times修改时乘标记的逆元))\)。
预处理逆元。
代码
#include
#include
#include
#include
#include
#include
#include
#include
#include